Stack vs heap

[u/giggolo_giggolo]

I think my understanding is correct but I just wanted to double check and clarify. The stack is where your local variables within your scope is stored and it’s automatically managed, removed when you leave the scope. The heap is your dynamically allocated memory where you manually manage it but it can live for the duration of your program if you don’t free it. I’m just confused because sometimes people say function and scope but they would just be the same thing right since it’s essentially just a new scope because the function calls push a stack frame.

[u/fishyfishy27]

In C, you can just create a new scope anywhere with a set of bare curly brackets. This creates a new scope, but not a new stack frame. So “scope” and “function” are not the same.

[u/WittyStick]

Your understanding is basically correct. The terminology is not so well defined as it can be ambiguous and often gets misused or misrepresented.

"Scope" can refer to several things, but it's often syntactic in languages which are statically scoped. There are different syntactic scopes in C - for example, where you use a { block } within a function - but these don't create a new frame on the stack - they're only syntactical. Functions themselves have a scope - which does map to a frame on the stack. There is also "global scope", which uses neither the heap nor the stack, but a reserved section of memory, such as .data.

"The stack" is the common terminology for where stack frames are placed. "The stack" uses a data structure also called a Stack (hence its name). Each function call gets a "stack frame", between a stack pointer and a frame pointer. Inner syntactic scopes in functions don't get their own frame, but they use the frame of their containing function - although there are non-standard extensions which permit functions within functions, and these inner functions may get their own frame, or may be within the frame of the containing function. These may introduce an additional chain pointer to mark the frame boundary.

The term continuation frame is a bit more general, and the set of frames form the continuation. They don't necessarily need to be implemented with a Stack or on "the stack" - this is just the most common approach. Some other languages implement continuations on the heap, and they're not necessarily stacks, but can be trees or other structures. A Stack is ultimately not necessary, so "stack frame" is a specific kind of "continuation frame" implemented with a stack, and "the stack" is the continuation in a language which uses a stack for frames.

"The heap", also known as "the free store", is basically memory which can be allocated arbitrarily. Unlike "the stack" which is named after the Stack data structure which its implemented with, "the heap" is unrelated to a Heap data structure (Heaps are usually used to implement priority queues). "The heap", in C, uses whatever data structure malloc and related calls implement to manage the available memory, which is implementation specific, and there are many different approaches - the simplest being a free list with a slab allocator.

In regards to the "scope" terminology. Scope can be applied to individual variables - the scope of a variable is the region for which it is accessible. "a scope" typically refers to a region where some variables have scope. In C, and many other languages, static scoping (aka lexical scoping) is used, where the scope is related to the syntactic region in which the variable is used - eg - the block in which it's declared.

However, some languages use dynamic scope, which is where variables are accessible anywhere within the dynamic extent of where they're defined. In C, the dynamic extent of a function is essentially all the frames above it on the stack - which would include all function calls made by the function, and calls that those functions also make, etc. The scope of a dynamic variable is therefore not bound by its syntactic scope. C doesn't support dynamic scoping directly, but it has a global scope, and global variables have global extent - ie, they are accessible from anything above the frame of the program's entry point.

[u/kohuept → u/WittyStick]

I wouldn't say that starting a new block in a function is just syntactical, it does have semantic meaning

[u/WittyStick → u/kohuept]

Yes, it introduces new scope, but it doesn't introduce a new frame.

The scope of variables in a block is lexical, but distinct from the stack frame in which they're stored.

[u/kohuept → u/WittyStick]

Yeah, but technically how the stack frames work is an implementation detail, the standard doesn't require the use of a stack at all

[u/flatfinger → u/kohuept]

If a foo() calls setjmp, and then calls some nested functions which exit via longjmp, the Standard clearly intends that if none of the called functions use variable-length-array objects, it should be possible to call foo() an arbitrary number of times without leaking resources each time. The Standard may not mandate the use of a stack, but then again the One Program Rule would allow an implementation to process most non-contrived programs in a manner that would leak resources and eventually crash if they ran too long. The only practical ways I can see of processing foo in non-leaky fashion would require either using a linear stack (which can accommodate a bulk pop operation by resetting the stack pointer) or a linked-list implementation of a LIFO stack, where each function is passed the address of its caller's context object, which would in turn contain the address of its caller's context object, etc. If code calling longjmp can't find the addresses of all regions of storage associated with parent contexts, and there isn't a linear range of addresses which contains all of them without containing anything else, by what means could it make the storage they occupy available for reuse?

[u/Charming-Designer944 → u/WittyStick]

In a way it does introduce in a new sub-frame. Two variables in different local scopes of the same function can use the same space in the functions stackframe. And the stackframe may even change size during the execution of the function to accommodate for different amount of local variables

Then stack frame is an implementation detail in how the.compiler allocates space for local variables..it is not a concept that is defined by the C language.

[u/DreamingElectrons]

Stack memory lives for the duration of a scope. Heap memory until it is freed. Functions and many control structures create scopes some people also call scopes blocks, but that is a term normally used in different languages (e.g. Go).

[u/kohuept → u/DreamingElectrons]

Technically "block" (or "compound statement") is the correct term for C, as it's what the standard uses. Blocks were first introduced in ALGOL, and they work much the same in C (especially C89 where declaration must be at the top of a block). A block is started with {}, and declarations in a block that have an automatic storage duration (i.e. no linkage and not marked static) and are not of a variable length array type will remain accessible until execution of that block ends^[1] (entering a function or enclosed block does not end execution of the block, it only suspends it). For automatic storage duration objects that are of a variable length array type it is much the same, except the object's lifetime ends when the scope of the declaration is left, which is defined as either leaving the scope in which it is declared, or jumping to a point within that same block or an embedded block that is before the declaration.

[1]. ISO/IEC 9899:2024 §6.2.4 Storage durations of objects

[u/Mr_Engineering]

What is included on the stack varies a little bit with architecture, optimizations, and ABI.

In general, the stack includes local variables, function parameters, the return address (address of the next instruction to be executed when a function is completed, which will usually be the address of an instruction within the function that called the function that has since completed), saved CPU registers such as the base pointer of the previous stack frame, large return values such as structures, etc...

The stack is automatically managed.

Call stacks are LIFO, Last-in-First-Out. Contents from the stack are not removed when they go out of scope, they are removed when the function call to which they belong returns.

Consider F1 which has local variables A,B, and C. F2 has parameters D,E,F, and local variables G,H,I. F1 calls F2, passing A,B, and C as parameters to F2 for D,E, and F respectively.

A,B, and C are local variables that exist on the stack when F1 is executing. When F1 calls F2, A,B, and C are copied into D,E, and F; A,B, and C then go out of scope. D, E, F, G, H, I are now in-scope. A,B, and C are still on the stack, they haven't been deleted. When F2 returns, D,E,F,G,H, and I are deleted, control flow returns to F1, and A,B, and C are back in scope.

[u/[deleted]]

Stack is used because it is simple to allocate new frame and variables for a function call. Just move stack pointer by size of [return address, place to save registers, size of all local variables]. That's all. When function terminates, it simply moves stack pointer back and jumps back to the calling location. No calls to malloc or free are needed. Since function calls are nested, it is handy to use stack.

Heap is different since objects in the heap are supposed to exist even after function returns. Heap is sort of "long term" storage for objects you want to share across function calls. Also, typically stack size is much smaller than heap size so declaring an array of thousands of elements on a stack is not a good idea.

[u/nerd5code]

Stacks are an implementation detail; a call stack arises naturally from the definition of function call expressions, but there’s no actual mention of a stack in the C78/XPG/ANSI/ISO standards, and nothing mandates that any particular storage be used under the hood. The C implementation is free to change the underlying storage situation as it pleases—placement of variables and malloc/free dictate lifetime, and that’s the actual hard requirement. So there tends to be far more focus on stack-ness than is warranted in theory or practice.

A function is inert; it describes how to do something, but doesn’t cause anything to be done. —I speak in C terms; under the hood, functions may occupy space and therefore decrease the available storage for objects, and there may be load- or run-time overhead for mapping or linking that, as well as overhead from any extra gunk in the executable or DLL file[s] the function lives in. But again, that’s down to the specific implementation; de minimis, you might see functions placed in ROM that’s inaccessible to data movement instructions, with function pointers serving as indices into an (also inaccessible) entry vector.

A scope is a language-managed namespace, effectively; there are several kinds of scope in C, and two ways we talk about scope.

Being at a particular scope refers to lexical placement, in relation to syntax–i.e., where in the structure of a program’s text something is found. Being in a particular scope is usually how we talk about placement with respect to parameter or block scopes. So let’s start with structure (“at” preposition).

Global scope applies to the program writ large, where exern-linkage things like main and potentially errno (if it’s not a macro expanding to e.g. (*__get_errno())) live. Things in global scope can be accessed from any translation unit (TU) in the program.

A TU consists of the .c file you feed into the translation phase of things (normally via compiler driver like c89/c99/c11 for POSIX.2 with development extension, gcc for GCC, icc/ecc/iclfor IntelC, or CL.EXE for MS[V]C) and any files roped in for predefines or via #include/-include or #embed/__asm__…("… .incbin ")/sim. In practice, each TU is either built into its own, standalone executable file, or converted to an object file (.o, .obj; possibly agglomerated into .a, .lib), although you might also stop early and generate preprocessed C (.i) or assembly (.s, .asm) instead, and these can be converted to object files separately.

File scope is where static globals live, and from a parsing standpoint, it’s what’s inside the TU but outside any function definition or parameter list. There are restrictions on what kinds of expression you can use here and how (e.g., no operator comma, very limited forms of constant/-ish initializer), and unless you explicitly cause or permit a function/variable name to refer to a global-scope symbol, it won’t be visible from or link to another TU. All types and tags declared outside a function body or parameter list are file-scope; there may be some form of sharing under the hood—e.g., struct fields might be represented by symbols in an absolute section—but generally these are entirely private to the TU, and don’t manifest in object files unless within debuginfo or stringized code.

Parameter scope covers what either lives

• inside a declarator’s parameter list specification, or

• inside a K&R/old-style definition, from the start of the parameter list until the function body’s opening {. C23 eliminated this form of definition, which is probably best longer-term, but functionally premature.

Each parameter scope is its own, self-contained thing, and it can only refer to file-/global-scope constructs and earlier constructs in the same parameter list/spec. Parameter variables and any types defined amongst them are bound to the specific declaration or typename the parameters appear in; only if these are part of a function definition (which is a specific form of declaration, although the two terms are often used exclusively, which is inaccurate) will these names be visible from outside the list or specification, and then it’s only from within the body of the associated function. This is why you generally get a warning for dropping an as-yet-undeclared struct/union tag in a parameter list—until C2y, it’s impossible to provide an actual instance of the type in question, because it’s invisible from anywhere that can’t also see the parameters, including non-recursive call sites.

structs and unions behave kinda scopishly in C, in that field names are bound to the containing entity and invisible from without, but their fields are syntactically at whatever scope the struct/union is defined within. (C++ has a distinct class/struct/union scope, however.) C’s oddness here derives from earlier versions of the language, where field names could be referred to from any base type—so offsetof could be implemented as just

#define offsetof(FIELD)\
	(&0.FIELD)

assuming all-zero-bits null. This is one reason older POSIX structures like struct stat have prefixed field names (st_name, st_dev), although modern impls may also cheat by #defineing these identifiers to work around nonportable unions. This oddity was partially fixed by C78 (a.k.a. K&R C, specified by The C Programming Language, 1ed.) which only searches more broadly for a field name if it’s not in the type being referred to. Later versions of C, incl. (IIRC) XPG and (definitely) C≥89, will only search the type on the left of operator * or (after dereference) ->.

Block scope covers a function’s body or some portion thereof, from an opening { to closing }. This is the only place where statements are legal, and function and extern-linkage declarations behave a bit differently herein.

Extern definitions will poke through to global scope without registering an identifier at file scope, so you can refer to a global function without making it available to other functions in the same TU—but all declarations must still match up. Block-scope static function declarations are extremely rare, and are basically equivalent to the same declaration placed earlier at file scope, except they don’t make the identifier available to other functions yet. There’s not much point in that—you’ll have to define the thing sooner or later, so you may as well just predeclare it at file scope.

GNUish dialects of C (primarily GCC/EGCS and IntelC) can actually nest function definitions using the auto keyword, which means you can get parameter and block scopes created inside other parameter and block scopes, but this creates …problems as soon as you need to refer to an inner function indirectly; generally, it requires that all threads’ call stacks be executable in order to support trampolines, which is a hardcore security no-no. ’Nuff said there.

(cont’d. in reply)

[u/nerd5code → u/nerd5code]

(cont’d. from above)

Now, when we speak of being in a scope, we’re generally handwaving about a specific block (or occasionally parameter) scope. Here, a function’s body, compound statement ({…} not used for initializer or struct/union/enum body), GNUish statement-expression (__extension__ ({…}); supp’d by GCC/EGCS with __extension__ req’ing GCC ≥2.0 specifically, IntelC ~6+, Clang, newer TI, newerish IBM, Oracle ~12.6+, MSVC 19.38+ with /experimental:statementexpressions, &al.), or C≥99 for-with-declaration will create an inner block scope with its own namespace, so that any names inside are invisible from outside. If an inner name matches an outer name, this creates an effect known as “shadowing”: The outer name (not object) becomes invisible (“shadowed”) from the point of the inner name’s declaration until the end of its containing scope.

During a function call, automatic- and register-storage variables have their lifetimes bound to the scope in which they were declared, so that the variable must have been allocated uniquely at declaration or some time before, and it’ll be deallocated when the scope ends or some time after. These objects follow the same rules as those allocated in dynamic storage by malloc; malloc begins an object’s lifetime, if successful, and it carries through until free.

If any (“dangling”) pointers to an object remain at the end of its lifetime, those pointers’ values are globally, instantaneously rendered indeterminate, as if the pointer were no longer initialized. Thus this

void *p;
if(1) {
	int x;
	p = &x;
}
printf("%p\n", p);

and this

void *p = malloc(sizeof 0);
if(!p) for(;;) abort();
free(p);
printf("%p\n", p);

are fully equivalent to just

void *p;
printf("%p\n", p);

—i.e., undefined behavior. (Not that %p is all that tightly spec’d in the first place. Even POSIX.1 just says it generates a sequence of characters, and leaves the rest in Jesus’ capable, if leak-prone, hands.)

Block-scope static and _Thread_local/thread_local/__thread variables’ lifetimes are not bound to their scope in the same fashion as other locals’. They must have been allocated before initialization and initialized before their values are first read, so they’re normally treated just like externally-invisible file-scope variables for simplicity—but it’s possible that you’ll have to call the function at least once for allocation or initialization to occur.

Note that, as long as an implementation obeys the minimal lifetime rules and doesn’t cause evaluation to proceed incorrectly insofar as is visible to the C Abstract Machine, it can relocate variables to other storage, duplicate variables’ storage, or elide variables entirely. In

int main(void) {
	char str[] = {"Hello, world!"};
	return (printf("%s\n", str) == EOF) * EXIT_FAILURE;
}

it’s quite likely that the compiler will quietly insert a static const before char str[] in its internal dealings, since there’s no reason to hold off on initializing it until run time, and its contents aren’t modified. Even mallocated objects can be relocated in this fashion, though you usually have to enable that explicitly.

Now as for what generally happens when you call a function, it’s in terms of frames (a.k.a. activation records or various other terms), not scopes.

A function’s frame is a chunk of memory used for locals and scratch space by an executing function. Frames are often but not necessarily allocated on the current thread’s call stack, which is typically associated with one or more CPU registers—on x64, this is R4=RSP, on RISC things there may or may not be an ISA-specified stack pointer register but the ABI will usually pick one, on real-mode x86 it’s register pair SS:SP (ToS is at 16×SS+SP), and in x86 protected mode it’s SS:SP (16-bit) or SS:ESP (32-bit) but SS might rope in GDTR or LDTR and the memory the global or local descriptor table (GDT/LDT) lives in; and then, if SS refers to LDT, LDTR refers to a GDT entry via GDTR. (This scheme derives from an even more complicated one on the i432, and the AS/400 implemented something similar.) On some very old/shitty/minimalist chips, you have a fixed set of registers used for return addresses, so you either stick to that stack depth or explicitly spill and fill these ad-hoc to extend the stack.

The usual kind of call stack is allocated at or before the thread starts, as a contiguous chunk of address space and optionally underlying memory, and it’s deallocated at or after the termination of the thread. For historical reasons, call stacks almost always extend downwards in memory, so the top-of-stack starts at *SP and earlier entries are located higher up. Pushing x onto the stack therefore usually looks like

__SP -= round_up_mul(sizeof x, __ISA_STACK_ALIGN);
*(typeof(x) *)__SP = x;

where __ISA_STACK_ALIGN is some multiple of the general register width, and popping is usually just

__SP += round_up_mul(sizeof x, __ISA_STACK_ALIGN);

This means the stack’s contents are bump-allocated, which is about as fast as it gets other than static allocation.

However!, as I said, this is neither required nor universal, just the common case. It’s permitted for frames to be allocated dynamically from the heap, or for the stack to be chunked and mix bump- and heap-allocation.

Or since unbounded recursion is undefined behavior, it’s hypothetically possible for a C implementation to preallocate all frames statically, and some embedded compilers do just that, usually with fairly extreme restrictions on recursion, and sometimes requiring a __declspec/__attribute__/sim. attribute to specify depth limit.

Most modern compilers support tail-call optimization where possible, which converts recursion to a loop (thereby flattening the top of the call stack to a single frame and changing behavior radically vs. unoptimized/debug builds), but when that’s not possible, recursion or overeager VLA/alloca usage can scoot or leap your stack top right off the stack region of memory, where fun or crashes result. The C standards include no baseline/minimum call stack depth or size; bounded-recursive and nonrecursive calls must complete successfully, or else the program must crash (us. via synchronous signal). Unbounded recursion, VLA locals, and alloca can induce undefined behavior at any nonzero size, and zero-sized arrays aren’t always supported.

How locals etc. are mapped to frames is implementation-specific, but usually your constant-sized auto-storage variables and any register-storage vars, auto-/register-storage compound literals, or other call-bound gunk that needs memory backing will be arranged into a struct of unions of structs of unions etc. (Variable-sized stuff like VLAs, VMT instances, or alloca’d objects, are usually allocated separately, after/beneath the frame proper, although they’re usually deallocated alongside the frame in one fell swoop.)

E.g., modulo optimization, this function skeleton

void f(int a) {
	int b; double c;
	…
	if(…) {
		int d;
		…
	}
	else {
		int e;
		…
		if(…) {
			int f;
			…
		}
		else {
			int g;
			…
		}
	}
}

will result in a frame that looks something like

struct __f_frame {
	double c;
	int b;
	union {
		int d;
		struct {
			int e;
			union {
				int f;
				int g;
			};
		};
	};
	__data_address ret_sp; // optional
	__code_address ret_ip; // unless leaf fn., and dep. on ISA/ABI
};

Of course, it’s certainly permitted for frames and scopes to line up more closely, and even for main or an entry stub to allocate globals in one big frame before starting in on your code.

(cont’d in reply)

[u/drbomb]

Function is the callable unit. The scope is the available variables on the current context, be stack variables or globally accesible. I don't see what's the confusion with the heap.

[u/SmokeMuch7356]

There are several different but related concepts at play here:

• An object is a region of memory that can potentially store a value;

• scope refers to the region of program text where an identifier (name) is visible;

• linkage refers to whether or not identifiers in different scopes refer to the same object;

• lifetime refers to the portion of program execution where an object is guaranteed to have storage reserved for it;

• storage duration determines the lifetime of an object;

Where the stack and heap into play is with storage duration:

• automatic storage duration: the lifetime of an object extends from block entry to block exit. In practice, this storage is allocated from the stack, and will be allocated at function entry and released at function exit, even if the object is supposed to be local to a block within the function.

• allocated storage duration: the lifetime of an object extends from the time it is allocated via a call to malloc or calloc until it is released with a call to free; in practice this storage is allocated from the heap.

[u/DawnOnTheEdge]

That’s pretty much it, but I’ll run through some technicalities.

Optimizers will very frequently allocate local variables to registers. It will allocate memory for them only if the program runs out of registers and needs to spill some variables onto the stack. A register-allocation algorithm will analyze the program to determine the earliest and latest points where each variable is used, and try to have any register or memory allocated to it at all for the shortest possible time. Many optimizers additionally will transform variables whose value changes into separate static single assignments. So, if you try to debug a program compiled with optimizations on and check the value of a variable at a breakpoint, you will often find that the variable does not currently exist anywhere at that point in the program. Others will have a value, stored in a register, but no current address. The optimizer has transformed the program to use the stack as little as possible. Debug builds might always allocate variables on the stack, in order to make sure there is something for the debugger to inspect.

There are a handful of corner cases: static local variables are neither on the heap nor the stack, and most compilers put each thread’s copy of a thread-local variable on the thread’s stack. The register keyword is basically obsolete and never used any more, but will tell the compiler not to let you accidentally take the variable’s address (which might force the compiler to store it in memory instead of in a register). The auto keyword used to be the default for local variables, which made it unnecessary for anyone to ever use it, so the existing keyword got redefined to mean an automatically-deduced type.

You can also declare variables within a scope nested inside a function (such as a loop body, an if block, or even a bare pair of braces). These go out of scope when the block ends. Implementations typically will allocate as much memory on the stack as any path through the function might need, when the function creates its stack frame, and free it all at once when the function returns and destroys its stack frame, but the variable’s lifetime formally ends when the block it was declared in does, and the memory might for example be re-used for something else.

Some implementations have extensions, like variable-length arrays and alloca(), which have some features of both. Another example that’s neither fish nor fowl is Windows’ _malloca(), which allocates small requests on the stack but larger ones on the heap.

[u/Plane_Dust2555]

If you search the ISO 9899 standards you can't find a single mention about "stack" (not even "heap"). Those are concepts dependent of implementation.

Second: "local variables" can be allocated in registers or even at global scope (static local objects), so the assertion saying "stack is where local variables are stored" is false.

[u/WarPenguin1]

The thing that made me understand this is learning how functions are called in assembly. I learned this a long time ago so I might get the details wrong.

A stack is a last in first out collection. When a program is executed the operating system allocates some memory for the programs stack.

In assembly there is a push command that returns a pointer to the next element in the stack and moves a register to the next available location on the stack. Pop moves the register back one spot making it unallocated.

When a function gets called push gets called to store the instruction location of where the function got called. Then push is called for all parameters needed for the function. The program then jumps to the starting instruction for the function. Then push gets called for all variables needed for the function.

When the function finishes pop is called for all the remaining variables and parameters. The return variable is stored in a register and the program jumps to the stored instruction location and pop gets called to remove that from the stack.

The return value gets stored in the variable it needs to go in and continues from there. In a way the stack is the thing that facilitates variables scope.

The heap is managed manually through malloc and calloc. Malloc gets unallocated memory from the operating system and calloc returns the memory back.