A function’s boxes vanish when it returns. So how can it build an array and hand it back? Watch the block under “Heap”.
Memory that outlives a function
make_squares builds an array on the heap and hands back its address
#include <stdio.h>#include <stdlib.h> int *make_squares(size_t n){ int *s = malloc(n * sizeof *s); if (s == NULL) return NULL; for (size_t i = 0; i < n; i++) s[i] = (int)(i * i); return s;} int main(void){ int *p = make_squares(4); if (p == NULL) return 1; for (size_t i = 0; i < 4; i++) printf("%d ", p[i]); printf("\n"); free(p); return 0;}Output
main has started. Its p has no value yet; first, main calls make_squares(4).
Describe this picture
The 24 lines of squares.c with the line about to run marked, beside a picture of memory in two parts: “Stack” on top and “Heap” below it, with a line between them. At the top of the stack is main’s card: p, an int * of 8 bytes at 0x7fe8, and below it i, a size_t of 8 bytes at 0x7fe0, which appears only while main’s loop runs. Below main’s card, while make_squares runs, is its own card: n, a size_t at 0x7fc8, s, an int * at 0x7fc0, and i at 0x7fb8 while its loop runs. Each box shows its type and name at the top left, its address at the top right, and its value in the middle, ”?” until a line writes one. Under the picture the program’s output appears once it prints, and under everything one sentence on the current step. The clip plays the program once, 28 steps in about 20 seconds, and rests on the end. At the call, make_squares’s card fades in with n holding 4. Line 6 opens a card titled “16 bytes” on the heap: four int boxes in two rows, 0x1000 and 0x1004 in the lower row and 0x1008 and 0x100c above them, each showing ”?”; 0x1000 flies into s and grows into an arrow from s down to the box at 0x1000. The loop fills the four boxes with 0, 1, 4 and 9, a dot running along the arrow each time. At the return, make_squares’s card fades out and the arrow now starts from main’s p, which holds 0x1000; the block stays as it was. main’s loop prints 0 1 4 9 into the output. Line 22, free(p);, hatches the block, empties its boxes and marks its card “freed”, and p’s arrow turns dashed while p still holds 0x1000; the clip holds there for 2.4 seconds. The box the last line wrote is outlined. The transport plays and pauses, steps one line back or forward, and scrubs; a paused step is kept in the page address as mem.step.
What outlives the call
The program prints 0 1 4 9 . The array was built inside make_squares, and main could still read it after make_squares had returned. Here is why.
The boxes of a function, its parameters and its variables, live in its frame on the stack, as on Functions and the call stack (1.3). n, s and i come into being with the call and are gone when it returns.
Line 6 asks for something else. malloc finds 16 bytes in another area of memory, the heap, and returns the address of the first one, 0x1000. That address goes into s, an ordinary pointer box in make_squares’s frame. The block itself is not in the frame.
Now watch the return. The frame goes, and s with it. But before it went, return s; handed the number 0x1000 back to main, and main stored it in p. The block on the heap never moved. Only the box holding its address changed, from s to p.
The block stays until the program gives it back. Line 22, free(p);, does that: the block is hatched, no longer the program’s to use. Look at p after it. p still holds 0x1000. free does not change p; it only gives back the block p points to.
Key idea
A stack variable lives as long as its function’s call. A heap block lives from malloc to free, whichever functions come and go in between.
The code and its cost
Asking for memory: malloc
int *s = malloc(n * sizeof *s);malloc(bytes) comes from <stdlib.h>. It asks for a block of that many bytes and returns its address. Here n is 4 and sizeof *s, the size of the box s points to, is 4, so the request is 16 bytes, room for four ints.
Write the size as n * sizeof *s rather than n * 4 or n * sizeof (int). If s’s type ever changes, to double * say, the size follows it, and nothing else needs editing.
malloc returns a void *: an address with no stated type. C converts it to int * when it is stored in s, with no cast needed.
The block’s contents are not set. Whatever bytes were there before are still there, which is why the picture shows ”?” until the loop writes each box.
When there is no memory: NULL
If no memory is left, malloc returns NULL instead of an address. A program must check before using the block, which is what lines 7 and 8 do: make_squares passes the NULL back, and main stops with return 1;. Following a NULL pointer stops the program, as on Pointers and addresses (2.1).
Line 10, s[i] = (int)(i * i);, has a cast. i is a size_t, the unsigned type used for sizes and counts, so i * i is a size_t too; (int) turns it into the int the box holds.
Giving it back: free
free(p) gives the block at p back, so that a later malloc can use those bytes again. Three rules go with it:
- Every block from
mallocis freed exactly once. - After
free(p), p still holds the old address, and that address must not be followed. Settingp = NULL;straight after makes the mistake easy to spot. - Only an address that
mallocreturned may be freed.
A block that is never freed, and whose address is lost, is a leak: the program can never use those bytes again, nor give them back. A program that runs for a long time and leaks a little on every pass grows until the machine runs out of memory. Memory errors (2.5) shows each mistake and the tools that catch them.
calloc and realloc
Two relatives of malloc come from the same header. calloc(n, size) asks for n boxes of size bytes and sets every byte to zero. With calloc(4, sizeof *s) in line 6, the four boxes would hold 0 0 0 0 before the loop runs. realloc(p, bytes) makes a block larger or smaller, keeping its contents; Dynamic arrays (5.6) grows an array with it.
How malloc finds free space inside the heap is the C library’s business; this course does not need it. In the pictures, blocks are numbered from 0x1000 in the order they are allocated.
Returning a local’s address is wrong
Here is make_squares written without the heap:
int *bad(void)
{
int local[4] = { 0, 1, 4, 9 };
return local;
}local lives in bad’s frame, and the frame is gone the moment bad returns. The address it hands back points at stack memory that the next call will reuse. gcc warns:
warning: function returns address of local variable [-Wreturn-local-addr]The values may even seem to be there for a moment, but nothing protects them. With the gcc used here, the function goes further and returns NULL, so a program that uses the result stops. Returning a heap address, as make_squares does, is right: the block stays until it is freed.
Stack against heap
| Feature | Stack | Heap |
|---|---|---|
| Made by | a call, for its variables | malloc (or calloc, realloc) |
| Lives until | the call returns | free |
| Size | small, and usually fixed when the program is written | chosen while the program runs |
| Given back | by the return, always | by free, or never: a leak |
A malloc costs more than a stack variable: the library has to find a free block, where a call’s frame only moves the stack down. A program that allocates often, one small block at a time, pays that cost on each.
Worked example
How many bytes. For double *p, malloc(1000000 * sizeof *p) asks for 1,000,000 × 8 = 8,000,000 bytes. For int *p, the same line asks for 1,000,000 × 4 = 4,000,000. The size follows p’s type.
A leak, counted. This main calls make_squares 500 times and throws each address away:
for (int k = 0; k < 500; k++)
make_squares(1000);Each call allocates 1,000 × 4 = 4,000 bytes, and none is freed, so 500 × 4,000 = 2,000,000 bytes leak. Built with -fsanitize=address, the program reports exactly that when it ends: 2000000 byte(s) leaked in 500 allocation(s).
Why big data goes on the heap. The stack is small. On the Linux systems this course uses, it is 8 MiB by default. A local int big[10000000]; needs 40,000,000 bytes, about 38 MiB, and a program that uses it stops with a segmentation fault. malloc(10000000 * sizeof *h) for the same 40,000,000 bytes succeeds.
Try it yourself. Once make_squares has returned, which box holds 0x1000? Only main’s p: s went with its frame. And after free(p)? p still holds 0x1000, though the block is no longer the program’s.
Where it’s used
Sizes known only at run time. A file read into memory, an image, a list that grows while the program runs: the program cannot know their sizes when it is written, so it asks the heap for them once it does.
Every node in this course. From Singly linked lists (7.1) on, each node of a list or a tree is its own block from malloc, freed when the node is removed.
Reference card
| Code or idea | Meaning |
|---|---|
p = malloc(n * sizeof *p); | asks for n boxes of p’s type on the heap; contents not set |
if (p == NULL) | no memory was left: check before using the block |
free(p); | gives the block back; p still holds the address |
p = NULL; | after free, so the old address cannot be followed by mistake |
calloc(n, size) | n boxes, every byte zero |
realloc(p, bytes) | a larger or smaller block, contents kept |
| leak | a block never freed whose address is lost |
| stack | a variable lives as long as its call |
| heap | a block lives from malloc to free |
| returning a local’s address | wrong: its frame is gone; return a heap address instead |
Platform: C11, gcc 13 on x86-64 Linux: int 4 bytes, size_t and pointers 8. The addresses in the pictures are short stand-ins, by one rule for the whole course: the stack from 0x7ff0 down, heap blocks numbered from 0x1000.