About C/C++ stack allocation

Question

While studying C++ (and C) I had some particular doubts regarding the working of stack allocation, that I can't find a solution to:

1. Does stack allocation call malloc/free functions implicitly? If not; how does it assure there is no conflict between stack allocation and heap allocation?

2. If yes; does stack allocation in C++ implicitly call new/delete too? If yes; does overloading the new operator for a class affect its stack allocation?

It yielded confusing results in VC++; but as VC++ isn't entirely standard-compliant (or so I heard) I decided I better ask here...

Solution 1

Stack allocation doesn't use anything like malloc/free. It uses a piece of memory called program stack which is just a contiguous segment of memory.

There's a special register that stores the top of the stack. When a new object is created on stack the top is raised thus increasing the stack, when an object is deallocated (goes out of scope) the top is lowered thus decreasing the stack.

If you try to allocate a too large object on stack or go too deep into recursion the top will outgrow the maximum allowed size of the stack and this is called stack overflow.

Note: actual direction of stack growth (increasing or decreasing addresses) will vary by system, but general idea is the same regardless of actual direction.

Solution 2

The answer to your first question is No. Stack is not allocated from the heap at all.

You should read What and where are the stack and heap first to understand the basic concepts.

Solution 3

There is a good question here:

"how does it assure there is no conflict between stack allocation and heap allocation?"

There is a single contiguous address space in almost all C/C++ implementations, so the stack and heap allocated memory do have to coexist in that space.

Although each time the stack grows and shrinks this is not done with individual heap allocations, you can still think of the stack as a single large block of memory allocated from the heap. If the stack grows beyond the boundary of that block, then we have a stack overflow (catchy name... someone should name a website after it).

In a multi-threaded program, each time a thread starts, a new stack has to be allocated for it, and when a thread dies the stack can be deallocated. And it would make sense for those whole-stack blocks to be allocated using the same heap management as is exposed through malloc/free.

So - very approximately speaking - you can think of the stack as being a type of object that coexists in the heap. A whole stack is malloc-ed all in one go, when a thread starts up, and then it gets suballocated from, and then it gets free-d in one go.

On Windows, you can (if you like to live dangerously) call the same virtual memory APIs yourself to find out about the stack and to force virtual page within it to be freed.

Solution 4

Stack allocation is typically done in terms of alloca() or implicitly by the compiler. A well-done alloca() will only require a scant few instructions, and there is no cost (or even a need) to free it when you're done.

You can pass a pointer to memory allocated by alloca() to any other function/method that expects a pointer. You MUST NEVER return a pointer allocated by alloca().

Here are some advantages and disadvantages to using stack allocation.

Solution 5

In C and C++, there are two types of memory allocation 'automatic', where the object is created for the lifetime of a function call, and 'dynamic', where some memory is allocated by a function provided by the runtime.

In the vast majority of runtime implementations, automatic objects are allocated using a contiguous stack provided by the operating system when the thread is created. The stack typically starts at a high valued address, and is decremented by the size of the object. Dynamic allocations (malloc in C, new in C++) use some other memory requested from the operating system. As the OS knows about the addresses the stack is using, it doesn't allocate the same addresses to the dynamic requests. As the dynamic area is not ordered, it is often called the heap.

So 'stack' allocation doesn't malloc/free. Automatic objects in C++ call the constructor and destructor, but not new or delete, as new and delete also have the code to manage dynamic memory.

View more solutions

Comments

[paxdiablo]

Actually, the two answers are "No" and "Not applicable" :-)

[Suma]

Voted up because of Stack Overflow, which is definitely welcome on this site.

[paxdiablo]

BTW, don't get hung up on the stack increasing and decreasing. On x86, the stack grows downward in memory to allocate space and upward to free it. See stackoverflow.com/questions/664744/… and its excellent accepted answer :-)

[sharptooth]

That's true and surely important, but it's not so critical for people who have no idea how stack allocation works.

[Leafy]

>> A whole stack is malloc-ed all in one go, when a thread starts up, and then it gets suballocated from, and then it gets free-d in one go. << That explains why there's no conflict I guess

[Leafy]

Oh yea, and I am aware that stack overflow has to do with the stack allocation; just that I didn't know how >__<

[Martin York]

This is the basic stack as tough at school. In real life things are more complex and the stack is not nesacerily a classic stack structure but can be interlaved into the heap.

[UserX]

Actually, in both cases, x86 and x86_64, the stack grows down. It means that ESP/RSP (stack pointer) gets decremented everytime something is allocated. You can create an stack allocator by allocationg nchar's and converting it's pointer to void or whatever you need. ``` ALLOC(size, T) alloc((char[sizesizeof(T)]{0x00})) void * alloc(char * obj) { return (void *)obj; } ```