How is heap and stack memories managed, implemented, allocated?

Question

In C/C++ we can store variables, functions, member functions, instances of a class either on a stack or a heap.

How is each implemented? How is it managed (high level)? Does gcc preallocates a chunk of memory to be used for the stack and heap, and then doles out on request? Is original memory coming from RAM?

Can a function be allocated on the heap instead of a stack?

Clarification

I am really asking about implementation and management of heap and stack memories. After reading referenced question, I didn't find anything that addresses that... thanks for the link

Preconcert

Dupe of https://mcmap.net/q/21727/-stack-static-and-heap-in-c among very many others – Grazing

Well, on a second thought, it is different, as I am really asking about implementation and management of heap and stack memories. After reading referenced question, I didn't find anything that addresses that... thanks for the link... – Preconcert

@ultraman: If it's different, please rewrite it to emphasize the differences. Don't comment on your question. It's yours. Rewrite it to get the information you actually want. – Caras

I'm not a big fan of closing questions, but this looks the same to me. Rephrase it to be different enough, and I may take my vote back. – Borsch

@Caras I will rewrite the subject, but I already ask in the question what I want.. exactly :) – Preconcert

@All done, so let me know. I welcome further edits... – Preconcert

Guys, can we please reopen the question? – Preconcert

I am a bit disappointed, about this question being closed. I wrote some explation for about 15 minutes and now I can throw it away. We can at least give some idea what it is all about and which books can be read to understand this. I vote to re-open the question. – Vandervelde

don't throw it away please post it in the comment or some such....click on reopen, and then post it here (I promise to vote up in the comment and answer) – Preconcert

I was also trying to come with an answer that explained in particular the stack in a bit more detail, but I don't have enough rep to vote for reopen. – Courier

@Martin Liversage and @Vandervelde please post the the answer in comments... thanks – Preconcert

Guys, if this question is not re-opened, I will open another one with the same content, please hold on to your answers, they will not go unheard, I swear... – Preconcert

Guys, 2 more reopen requests are needed. We're almost there... – Preconcert

I also don't have enough rep to vote for reopen. – Vandervelde

15 more minutes and a new one will open.... – Preconcert

@Martin Liversage and @Vandervelde and others, new Question is here: #1213765.. this one will be deleted in 5 mintues. thanks – Preconcert

Answer 1

Modern operating systems do not give you direct access to hardware RAM and instead abstract it in so called virtual memory, which it maps to RAM on demand. Each process is usually given its own private copy of the complete address space. This allows the OS to move a process' memory around in RAM at runtime or even swap it out to disk. This happens transparently, i.e. a process is not notified of such a relocation and needs not have code to handle this. (Some real time applications might use techniques to prevent having its memory swapped out).

When linking object files to an executable or a dynamic library, the linker statically allocates memory for the cpu instructions of a function/method and for all global variables. When the os loads the executable or dynamic library, it maps this pre-allocated memory into real memory.

On startup, each thread receives a private memory area called the stack. Each time you call a function/method, the compiler inserts code to automatically allocate (by incrementing the stack pointer) enough memory from the stack to hold all parameters, local variables and the return value (if any) the function/method uses. If the compiler determines that it is sufficient to leave some variables in processor registers, it does not allocate memory on the stack for it. When the function/method returns, it runs code generated by the compiler to free (by decrementing the stack pointer) this memory. Note that the destructors of any objects on the stack will be called when the block they are defined in exits, which might be a long time before returning. Also, the compiler is free to reuse the alloacated memory as it sees fit.

When an exception is thrown, the compiler compiler inserts special code that knows the layout of the stack and that can unwind it until finding a suitable exception handler.

As opposed to this, memory on the heap is allocated using new / delete, for which the compiler inserts code to request or release memory using a system library.

Please note that this is a simplified description to give you an idea of how memory allocation works.

Proteolysis

Answer 2

Basically the heap is not implemented by the compiler, but instead by the C runtime library. Obviously this code is very platform dependent. On Unix or Unix-like systems the implementation is generally based on the sbrk/brk system call and a bigger amount of memory is allocated to reduce the number of system calls. This memory is then managed by the heap memory manager. If more memory is required a new call to sbrk is is issued. The current end address of the heap can be obtained with sbrk(0) if you are interested in debugging the heap management routines. Most memory managers to do not return memory to the OS during the lifetime of a process (gnu c runtime library does if certain constraints are met).

A more detailed description is available in http://gee.cs.oswego.edu/dl/html/malloc.html.

Chalmer

This is not always the case. On OSes that are capable enough, the CRT doesn't have to. Similar with the stack: if the OS is capable enough, the compiler doesn't have to do as much. The case that the OS can handle the stack but not the heap is common but not universal. – Grater

I feel quite sure that MSVC returns most memory to the OS, when it can. – Seismic

Answer 3

Some very interesting reading

FreeRTOS: Memory Management

Arm C and C++ Libraries and Floating-Point Support User Guide

2.13.2 Choosing a heap implementation for memory allocation functions

malloc(), realloc(), calloc(), and free() are built on a heap abstract data type. You can choose between Heap1 or Heap2, the two provided heap implementations.

The available heap implementations are:

• Heap1, the default implementation, implements the smallest and simplest heap manager.

• Heap2 provides an implementation with the performance cost of malloc() or free() growing logarithmically with the number of free blocks.

Heap1, the default implementation, implements the smallest and simplest heap manager. The heap is managed as a single-linked list of free blocks that are held in increasing address order. This implementation has low overheads. However, the performance cost of malloc() or free() grows linearly with the number of free blocks and might be too slow for some use cases.

If you expect more than 100 unallocated blocks, Arm recommends that you use Heap2 when you require near constant-time performance.

Heap2 provides an implementation with the performance cost of malloc() or free() growing logarithmically with the number of free blocks. Heap2 is recommended when you require near constant-time performance in the presence of hundreds of free blocks.

Organelle