Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can a stack underflow happen in C++?

What is a simple example in C++ that causes a stack underflow in the case of invoking and returning from method calls?

I am familiar with the calling convention, i.e thiscall, stdcall and the cdecl and way they would clean the stack. Wouldn't a stack underflow automatically be taken care of by the code generated by the compiler?

What are the situations that can get me into trouble with stack underflow?

like image 365
Vishnu Pedireddi Avatar asked Jul 01 '11 18:07

Vishnu Pedireddi


People also ask

How does stack underflow occur?

Stack Underflow & Overflow Stack underflow happens when we try to pop (remove) an item from the stack, when nothing is actually there to remove. This will raise an alarm of sorts in the computer because we told it to do something that cannot be done.

What is stack underflow in programming?

An error condition that occurs when an item is called for from the stack, but the stack is empty.

What are the conditions for stack underflow & stack overflow?

The underflow condition checks if there exists any item before popping from the stack. An empty one cannot be popped further. The overflow condition checks if the stack is full (or more memory is available) before pushing any element. This prevents any error if more space cannot be allocated for the next item.

How can we Minimise the stack overflow?

One method to prevent stack overflow is to track the stack pointer with test and measurement methods. Use timer interrupts that periodically check the location of the stack pointer, record the largest value, and watch that it does not grow beyond that value.


2 Answers

The only way I can see this actually happening would be if you declared a function to use the stdcall (or any other calling convention that specifies the callee clean the stack) and then invoke the function through a function pointer that was specified as a cdecl (or any other calling convention where the stack is cleaned by the caller). If you do that, the called function will pop the stack before returning and then the caller would also pop the stack leading to underflow and terrible things.

In the specific case of member functions, the calling convention is usually referred to as thiscall and whether the caller or the callee cleans the stack depends on the compiler.

See here for details of calling conventions.

like image 167
Sean Avatar answered Sep 21 '22 22:09

Sean


I am not sure if you are talking of the data structure stack and the underflow problem in it or something else. As far as the stack(data structure) underflow problem is concerned here is a explanation.

stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top.

The push operation adds a new item to the top of the stack, or initializes the stack if it is empty. If the stack is full and does not contain enough space to accept the given item, the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack.

A pop either reveals previously concealed items, or results in an empty stack, but if the stack is empty then it goes into underflow state (It means no items are present in stack to be removed).

The stack top operation gets the data from the top-most position and returns it to the user without deleting it. The same underflow state can also occur in stack top operation if stack is empty.

Consider a stack implementation example:

template <class Item> class Stack 
{
public:
    bool isEmpty() const;
    size_t size() const;
    Item pop();
    void push(const Item& it);
private:

};

Now consider the following operations being performed on this stack.

C++ command                      resulting stack
------------------------------------------------
Stack<int> S;
                                  _____ (empty stack of ints)



S.push(7);                            
                                  | 7 |  <-- top
                                  -----

S.push(2);                            
                                  | 2 |  <-- top 
                                  | 7 |
                                  -----

S.push(73);                           
                                  |73 |  <-- top 
                                  | 2 |
                                  | 7 |
                                  -----

S.pop();                           
                                  | 2 |  <-- top
                                  | 7 |                    -----
S.pop();      
                                  -----
S.pop();                           
                                  | 7 |  <-- top
                                  -----
S.pop();                           
                                  -----  (empty)

S.pop();                           
                    ERROR "stack underflow"
like image 37
Alok Save Avatar answered Sep 21 '22 22:09

Alok Save