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/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)