Who is responsible for the stack and heap in C++?

Question

This isn't a question of what the purpose of either of them are. Instead it's a question of who or what is responsible for the invention of the stack and heap?

Are these inventions of the C++ compiler?

Does the os specify memory sections in RAM designated "stack" and "heap"?

I'm pretty sure they are not built into the hardware but I could be wrong.

Also, is the compiler responsible for generating assembly code that specify which local or function data will be stored on the stack vs CPU registers?

Answer 1

Who or what is responsible for the invention of the stack and heap?

As far as inventing a stack and heap, you would have better luck searching the web. Those concepts have been around for many decades.

Are these inventions of the C++ compiler?

Perhaps invention is the wrong term here. They are data structures. The compiler and OS (if present) are in charge of organizing and utilizing memory.

Does the os specify memory sections in RAM designated "stack" and "heap"?

This is OS specific and can vary by OS. Some OSes reserve stack and heap areas, others don't.

In the embedded system I am working on, there are two heap areas: 1) The area specified in the linker, 2) A portion of the memory allocated to the OS. Both of these areas are set to zero size, so we don't have any heaps.

The stack areas are set up by initialization code that runs before the C language Run-Time Library is initialized. The RTL code may also create some stack areas as well. Our RTOS also creates stack areas (one for each task).

So, there is not one single area called the stack. Some platform's don't use a stack concept at all (especially those whose memory capacity is severely restricted).

I'm pretty sure they are not built into the hardware but I could be wrong.

Depends on the hardware. Simple and cheap hardware only allocates an area of RAM (read/write memory). More complex and expensive hardware may allocate separate areas for stacks, heaps, executables and data. Constants may be placed into ROM (read-only memory, such as Flash). There is no one-size or one-configuration that supports everything. Desktop computers are different animals than smaller embedded systems.

Also, is the compiler responsible for generating assembly code that specify which local or function data will be stored on the stack vs CPU registers?

The task can be in the Linker or Compiler or both.
Many compiler tool-chains utilize both stack and CPU registers. Many variables and data can be on the stack, in registers, in RAM or in ROM. A compiler is designed to make best use of the platform's resources, including memory and registers.

A good example to study is the assembly language generated by your compiler. Also look at the linker instruction file as well. The use of registers or stack memory is so dependent on the data structures (and types) that it may be different for different functions. Another factor is the amount of memory and kind available. If the processor has few registers available, the compiler may pass variables using the stack. Larger data (that doesn't fit in a register) may be passed on the stack or a pointer passed to the data. There are too many options and combinations available to enumerate here.

Summary

In order for the C and C++ languages to be very portable, many concepts are delegated to the implementation (compiler / toolchain). Two of these concepts are commonly referred to as stack and heap. The C and C++ language standards use a simple model as the environment for the languages. Also, there are terms such as "hosted" and "semihosted" which indicate the degree that a platform supports the language requirements. The stack and heap are data structures not required by the platform in order to support the languages. They do assist in the efficiency of the implementation.

If stacks and heaps are supported, their location and management is the responsibility of the implementation (toolchain). A compiler is free to use it's own memory management functions or the OS (if present). The management of the stacks and heaps may require hardware support (such as virtual memory management or paging; and fences). There is no requirement for the stack to grow towards the heap. There is no requirement for the stack to grow in a positive direction. These are all up to the implementation (toolchain), and they can implement and locate stacks however and wherever they like. Note: most likely, they won't place variables in read-only memory and won't locate stacks outside memory capacity.

Answer 2

This post is about 32-bit Linux on x86. I don't know about other architectures/OSes.

Are these inventions of the C++ compiler? Does the [OS] specify memory sections in RAM designated "stack" and "heap"?

Heap or free store

A program has different sections, one of them the .data section. Dynamic memory allocation is usually implemented using the brk system call (sbrk builds on top of it). man brk says the following:

brk() and sbrk() change the location of the program break, which defines the end of the process's data segment (i.e., the program break is the first location after the end of the uninitialized data segment). Increasing the program break has the effect of allocating memory to the process; decreasing the break deallocates memory.

That means the "heap" or "free store" is in reality the .data section.

As @kfx said in the comments to this answer, no standard states that malloc has to be implemented using brk. An implementation using mmap is possible as well. From man mmap:

The mmap() function shall establish a mapping between an address space of a process and a memory object.

This basically means that a file (Unix ideology: "everything is a file") is mapped into memory.

Stack

The stack is also in the .data section and grows downward. Technically, x86 enables you to define a downward-growing stack segment but Linux does not use this feature. Dunno why.

I'm pretty sure they are not built into the hardware but I could be wrong.

No, they aren't. Segments are set up at runtime of the OS and not stored in the hardware.

---

The following is from Linux 4.2.

When the MBR has jumped to the bootloader and the bootloader has executed, this is executed (the path is /arch/x86/boot/header.S):

# Normalize the start address
    ljmp    $BOOTSEG, $start2

start2:
    movw    %cs, %ax
    movw    %ax, %ds
    movw    %ax, %es
    movw    %ax, %ss
    xorw    %sp, %sp

All those segment registers are initialized to $BOOTSEG here, which is 0x7c0. sp is set to 0x00. No esp since we're still in Real Mode!

After the initialization stuff is done, the jump into the real kernel is performed. The segment registers are set up as follows:

movw    $__BOOT_DS, %cx
movw    $__BOOT_TSS, %di

movl    %cr0, %edx
orb $X86_CR0_PE, %dl    # Protected mode
movl    %edx, %cr0

# Transition to 32-bit mode
.byte   0x66, 0xea      # ljmpl opcode
2:  .long   in_pm32         # offset
.word   __BOOT_CS       # segment
ENDPROC(protected_mode_jump)

.code32
.section ".text32","ax"
GLOBAL(in_pm32)
# Set up data segments for flat 32-bit mode
movl    %ecx, %ds
movl    %ecx, %es
movl    %ecx, %fs
movl    %ecx, %gs
movl    %ecx, %ss

The segment registers are set to the content of cs again.

---

Also, is the compiler responsible for generating assembly code that specify which local or function data will be stored on the stack vs CPU registers?

Yes. For function invocations, there are different calling conventions: some push their arguments onto the stack, some move them into registers.
Local variables can be implemented with registers or the stack as well.
Unoptimized C compilers push the arguments onto the stack, call the function, and pop them off afterwards ("stdcall" calling convention).
They use the stack for local variables, in combination with the ebp register.

Answer 3

That is implementation defined (C/C++ is not aware of any hardware)

Answer 4

As @chux mentions, you can write C or C++ code that runs on the 'bare metal' without any operating system at all. Looking at how that works may help understand where the responsibility for stack and heap can lie.

The heap is easiest to explain. Every time you new or delete an object (or call malloc/free) the compiler generates code that calls the allocation/deallocation functions. (typically, new will often end up calling malloc). So the compiler's resopnsibility is just to generate calls to those two functions.

The initial space allocated for the heap is either determined by the OS when the program runs, or (in bare metal code) by the programmer who specifies it as part of the linker setup.

So where are those functions, and what do they do? Typically they're part of the runtime library that's linked with your compiled code (and they're often written in C or C++). On 'bare metal' systems they manage the heap directly - which is just an area of memory as far as the CPU is concerned. CPUs don't have any concept of a heap. If there's an operating system involved, these functions often just call heap management functions provided by the OS. Sometimes, it's a mixture, as the library may manage it's own heap, but may make calls to the OS to get further chunks of memory if it runs out.

The stack is different. Pretty much every CPU does have the concept of a stack in hardware (although the stack just lives in normal memory). As you call functions and allocate stack-based variables, the compiler generates the code to manipulate the 'stack pointer' (a special CPU register) accordingly. With multi-threaded code, each thread has it's own stack, and the multi-tasking kernel of the OS is responsible for switching to the appropriate stack for each task.

Just to further confuse you, in multi-threaded systems, the stack space for each thread is often allocated from the heap.

Answer 5

Does the os specify memory sections in RAM designated "stack" and "heap"?

Yes, for every program, the OS allocates, for the data:

• a stack for local variables
• a static memory for static data (global variables or variable explicitely declared static)
• and a heap for dynamic memory management

I'm pretty sure they are not built into the hardware

Hardware is agnostic about the memory layout. It provides memory and the OS does the rest. However, on x86/x64 and many other CPU architectures for example, though the CPU still not impose a stack, it provides dedicated registries and instructions to manage a stack, only the stack, because it's a very important feature.

Also, does the compiler generate assembly code that specifies what information will be stored on the stack vs what maybe stored on a CPU's registers?

These information are produced by the linker, not the compiler, and they're stored in the executable file header, not in the assembler code.

EDIT: In fact I already answered to this with 'Does the os specify memory sections in RAM designated "stack" and "heap"?'. But I've read "where" instead of "what". Sorry for that.

Answer 6

You're mistaken. Stack and heap did not originate in C or C++. They originated due to physical memory architectures in early machines.

I'll give the rough story (I'm sure there are plenty of specifics that I'm missing, glossing over, etc) for x86 hardware. I gather there was a similar evolution with other hardware families, but am less familiar with those.

Early PCs had 640K or less of total memory, in which programs could be loaded (from a floppy drive with capacity of a few hundred K) and executed. This area of memory was later referred to as "conventional memory". When early PCs were developed, it was believed this amount of memory was probably more than would ever be needed.

In what was, at the time, a significant step forward, the physical memory was increased from 640K to 1MB, using an expansion card. There were a number of incompatible variants. The most widely used was based on an Expanded Memory Specification developed jointly by Microsoft, Intel, and a couple of other companies. This was named expanded memory.

Then came the 286 CPU, with support for protected mode, and ability to address more than 1MB of memory - up to 64MB. Additional physical banks of memory (physically separate chipsets) were used to install additional memory. In the original implementations, this memory was slower than conventional memory, but cheaper in larger amounts. It was referred to by various names, such as extended memory (the XMS specification) or high memory (named after the name of one of the device drivers to access it). Later versions of the XMS specification allowed addressing of up to 4GB of memory (i.e. 32 bit memory).

Conventional and Expanded memory were necessary for programs to run - if there wasn't enough of these available to load executable code, the program simply could not execute. This was referred to it as the stack - simply a collective term for conventional memory, expanded memory, and similar types of memory managed by drivers from other (non-Intel, non-Microsoft) vendors. It was also managed by programs using a LIFO stack approach (e.g. when a function called, context placed on a stack data structure, and popped when the function returned). In a language like C, local and global variables were allocated on the "stack". Because of the small amount available (1MB or less on any system) this memory was always at a premium.

Extended memory was originally used for additional memory needs of the program to store data. As I said above, this memory was originally physically slower, but cheaper in larger amounts. It was managed with help of various device drivers (himem.sys, etc), where each device driver provided a distinct and incompatible API. The heap was originally a collective term for all of this additional memory, regardless of what device driver was used to manage it. Languages/libraries at the time which supported dynamic memory allocation (with C, malloc(), free(), etc) typically did so using extended memory (with some fallbacks if that memory was not physically available) and handled the details of communicating with the range of possible device drivers. Some compilers that supported languages with pointers (or similar constructs) used distinct pointer types to refer to stack or heap (near and far pointers, respectively in early versions of XMS, and in later versions of XMS [which addressed up to 4GB] huge pointers).

Over time, as hardware technology evolved, the distinction between types of physical memory disappeared - all memory (other than CPU cache and the like) was physically the same type of memory, on a given machine (or the chipset mediated and provided a uniform memory interface, even if there were physical banks of distinct memory). Operating systems (unix, 32 bit windows, etc), for the purpose of managing processes, tended to reserve parts of memory akin to the stack (the basic memory needed to execute a program) and enforce limits on this using quotas. With modern operating systems, this is often referred to now as the stack, but (thanks to wonder of techniques like virtual memory management) is allocated to processes rather than on a system-wide basis, and the heap refers to other memory available to a process that a program can dynamically allocate.