CS107, Lecture 7

Stack and Heap

Reading: K&R 5.6-5.9 or Essential C section 6 on

the heap

This document is copyright (C) Stanford Computer Science and Nick Troccoli, licensed under Creative Commons Attribution 2.5 License. All rights reserved.
Based on slides created by Marty Stepp, Cynthia Lee, Chris Gregg, Lisa Yan, Jerry Cain and others.
1
 Lecture Plan
• The Stack
• The Heap and Dynamic Memory
• Practice: Pig Latin
• realloc
• Practice: Pig Latin Part 2

cp -r /afs/ir/class/cs107/lecture-code/lect7 .
2
 Lecture Plan
• The Stack
• The Heap and Dynamic Memory
• Practice: Pig Latin
• realloc
• Practice: Pig Latin Part 2

3
 Memory Layout
• We are going to dive deeper into different areas of
memory used by our programs.
• The stack is the place where all local variables and
parameters live for each function. A function’s stack
“frame” goes away when the function returns.
• The stack grows downwards when a new function is
called and shrinks upwards when the function is
finished.

4
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack argc: 1

int c = 99;
func2(); argv: 0xfff0
}

int main(int argc, char *argv[]) {

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

5
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); argv: 0xfff0
}

int main(int argc, char *argv[]) {

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

6
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
}

int main(int argc, char *argv[]) {

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

7
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
}

int main(int argc, char *argv[]) {

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

8
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
} func1

int main(int argc, char *argv[]) {

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

9
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
} func1

int main(int argc, char *argv[]) { c: 99

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

10
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
} func1

int main(int argc, char *argv[]) { c: 99

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

11
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
} func1

int main(int argc, char *argv[]) { c: 99

int a = 42;
int b = 17;
func1(); func2
printf("Done.");
return 0;
}

12
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
} func1

int main(int argc, char *argv[]) { c: 99

int a = 42;
int b = 17;
func1(); func2
printf("Done.");
return 0; d: 0
}

13
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
} func1

int main(int argc, char *argv[]) { c: 99

int a = 42;
int b = 17;
func1(); func2
printf("Done.");
return 0; d: 0
}

14
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
} func1

int main(int argc, char *argv[]) { c: 99

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

15
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
} func1

int main(int argc, char *argv[]) { c: 99

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

16
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
}

int main(int argc, char *argv[]) {

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

17
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
}

int main(int argc, char *argv[]) {

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

18
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
}

int main(int argc, char *argv[]) {

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

19
0x0
 The Stack
Memory
void func2() {
int d = 0;
} main

void func1() { Stack a: 42 argc: 1

int c = 99;
func2(); b: 17 argv: 0xfff0
}

int main(int argc, char *argv[]) {

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

20
0x0
 The Stack
Memory
void func2() {
int d = 0;
}

void func1() {
int c = 99;
func2();
}

int main(int argc, char *argv[]) {

int a = 42;
int b = 17;
func1();
printf("Done.");
return 0;
}

21
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else {
return n * factorial(n – 1);
}
}

int main(int argc, char *argv[]) {

printf("%d", factorial(4));
return 0;
}

22
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else {
return n * factorial(n – 1);
}
}

int main(int argc, char *argv[]) {

printf("%d", factorial(4));
return 0;
}

23
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else { factorial
return n * factorial(n – 1); n: 4
}
}

int main(int argc, char *argv[]) {

printf("%d", factorial(4));
return 0;
}

24
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else { factorial
return n * factorial(n – 1); n: 4
}
}

int main(int argc, char *argv[]) {

printf("%d", factorial(4));
return 0;
}

25
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else { factorial
return n * factorial(n – 1); n: 4
}
} factorial
n: 3
int main(int argc, char *argv[]) {
printf("%d", factorial(4));
return 0;
}

26
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else { factorial
return n * factorial(n – 1); n: 4
}
} factorial
n: 3
int main(int argc, char *argv[]) {
printf("%d", factorial(4));
return 0;
}

27
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else { factorial
return n * factorial(n – 1); n: 4
}
} factorial
n: 3
int main(int argc, char *argv[]) {
printf("%d", factorial(4)); factorial
return 0; n: 2
}

28
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else { factorial
return n * factorial(n – 1); n: 4
}
} factorial
n: 3
int main(int argc, char *argv[]) {
printf("%d", factorial(4)); factorial
return 0; n: 2
}

29
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else { factorial
return n * factorial(n – 1); n: 4
}
} factorial
n: 3
int main(int argc, char *argv[]) {
printf("%d", factorial(4)); factorial
return 0; n: 2
}
factorial
n: 1

30
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else { factorial
return n * factorial(n – 1); n: 4
}
} factorial
n: 3
int main(int argc, char *argv[]) {
printf("%d", factorial(4)); factorial
return 0; n: 2
}
Returns 1 factorial
n: 1

31
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else { factorial
return n * factorial(n – 1); n: 4
}
} factorial
n: 3
int main(int argc, char *argv[]) {
printf("%d", factorial(4)); Returns 2 factorial
return 0; n: 2
}

32
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else { factorial
return n * factorial(n – 1); n: 4
}
} Returns 6 factorial
n: 3
int main(int argc, char *argv[]) {
printf("%d", factorial(4));
return 0;
}

33
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else { factorial
return n * factorial(n – 1); Returns 24
n: 4
}
}

int main(int argc, char *argv[]) {

printf("%d", factorial(4));
return 0;
}

34
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else {
return n * factorial(n – 1);
}
}

int main(int argc, char *argv[]) {

printf("%d", factorial(4));
return 0;
}

35
0x0
 The Stack
Memory
Each function call has its own stack frame for its own copy of
variables.
main
int factorial(int n) { argc:
1
if (n == 1) { Stack
return 1; argv: 0xfff0
} else {
return n * factorial(n – 1);
}
}

int main(int argc, char *argv[]) {

printf("%d", factorial(4));
return 0;
}

36
0x0
 The Stack
• The stack behaves like a…well…stack! A new function call pushes on a new
frame. A completed function call pops off the most recent frame.
• Interesting fact: C does not clear out memory when a function’s frame is
removed. Instead, it just marks that memory as usable for the next function
call. This is more efficient!
• A stack overflow is when you use up all stack memory. E.g. a recursive call
with too many function calls.
• What are the limitations of the stack?

37
 The Stack
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc:
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str;
}

int main(int argc, char *argv[]) {

char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
return 0;
}

38
0x0
 The Stack
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc: str:
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str;
}

int main(int argc, char *argv[]) {

char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
return 0;
}

39
0x0
 The Stack
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc: str:
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str; create_string
ch: 'a' num: 4
}

int main(int argc, char *argv[]) {

char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
return 0;
}

40
0x0
 The Stack
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc: str:
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str; create_string
ch: 'a' num: 4
}

int main(int argc, char *argv[]) {

char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
return 0;
}
new_str:

41
0x0
 The Stack
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc: str:
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str; create_string
ch: 'a' num: 4
}

int main(int argc, char *argv[]) { '\0'

char *str = create_string('a', 4); 'a'
printf("%s", str); // want "aaaa" 'a'
return 0; 'a'
}
new_str: 'a'

42
0x0
 The Stack
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc: str:
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str; create_string
ch: 'a' num: 4
}

int main(int argc, char *argv[]) { Returns e.g. 0xff50 '\0'

char *str = create_string('a', 4); 'a'
printf("%s", str); // want "aaaa" 'a'
return 0; 'a'
}
new_str: 'a'

43
0x0
 The Stack
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc: str: 0xff50
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str; create_string
ch: 'a' num: 4
}

int main(int argc, char *argv[]) { '\0'

char *str = create_string('a', 4); 'a'
printf("%s", str); // want "aaaa" 'a'
return 0; 'a'
}
new_str: 'a'

44
0x0
 The Stack
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc: str: 0xff50
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str;
}

int main(int argc, char *argv[]) {

char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
return 0;
}

45
0x0
 The Stack
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc: str: 0xff50
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str;
}

int main(int argc, char *argv[]) {

char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
return 0;
}
Problem: local variables go away when a function
finishes. These characters will thus no longer exist,
and the address will be for unknown memory!
46
0x0
 The Stack
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc: str: 0xff50
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str;
}

int main(int argc, char *argv[]) {

char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
return 0;
}

47
0x0
 Stacked Against Us

This is a problem! We need a way to have

memory that doesn’t get cleaned up when
a function exits.

48
 Lecture Plan
• The Stack
• The Heap and Dynamic Memory
• Practice: Pig Latin
• realloc
• Practice: Pig Latin Part 2

49
 The Heap
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc: str:
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str; create_string
ch: 'a' num: 4
}

int main(int argc, char *argv[]) { '\0'

char *str = create_string('a', 4); 'a'
printf("%s", str); // want "aaaa" 'a'
return 0; Us: hey C, is there a way to 'a'
} make this variable in memory
new_str: 'a'
that isn’t automatically
cleaned up?
50
0x0
 The Heap
Memory
char *create_string(char ch, int num) {
char new_str[num + 1];
for (int i = 0; i < num; i++) { main
argc: str:
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str; create_string
ch: 'a' num: 4
}

int main(int argc, char *argv[]) { '\0'

char *str = create_string('a', 4); 'a'
printf("%s", str); // want "aaaa" 'a'
return 0; 'a'
}
C: sure, but since I don’t know new_str: 'a'
when to clean it up anymore,
it’s your responsibility…
51
0x0
 The Heap
• The heap is a part of memory that you can
manage yourself.
• The heap is a part of memory below the stack
that you can manage yourself. Unlike the stack,
the memory only goes away when you delete it
yourself.
• Unlike the stack, the heap grows upwards as
more memory is allocated.

The heap is dynamic memory – memory that can

be allocated, resized, and freed during program
runtime.
52
 malloc
void *malloc(size_t size);
To allocate memory on the heap, use the malloc function (“memory allocate”)
and specify the number of bytes you’d like.

• This function returns a pointer to the starting address of the new memory. It
doesn’t know or care whether it will be used as an array, a single block of
memory, etc.
• void *means a pointer to generic memory. You can set another pointer
equal to it without any casting.
• The memory is not cleared out before being allocated to you!
• If malloc returns NULL, then there wasn’t enough memory for this request.
53
 The Heap
Memory
char *create_string(char ch, int num) {
char *new_str = malloc(sizeof(char) * (num + 1));
for (int i = 0; i < num; i++) { main
argc: str:
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str; create_string
ch: 'a' num: 4
}
new_str: 0xed0
int main(int argc, char *argv[]) {
char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
'\0'
return 0;
Heap 'a'
}
'a'
'a'
'a'
54
0x0
 The Heap
Memory
char *create_string(char ch, int num) {
char *new_str = malloc(sizeof(char) * (num + 1));
for (int i = 0; i < num; i++) { main
argc: str:
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0'; Returns e.g. 0xed0
return new_str; create_string
ch: 'a' num: 4
}
new_str: 0xed0
int main(int argc, char *argv[]) {
char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
'\0'
return 0;
Heap 'a'
}
'a'
'a'
'a'
55
0x0
 The Heap
Memory
char *create_string(char ch, int num) {
char *new_str = malloc(sizeof(char) * (num + 1));
for (int i = 0; i < num; i++) { main
argc: str: 0xed0
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0'; Returns e.g. 0xed0
return new_str; create_string
ch: 'a' num: 4
}
new_str: 0xed0
int main(int argc, char *argv[]) {
char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
'\0'
return 0;
Heap 'a'
}
'a'
'a'
'a'
56
0x0
 The Heap
Memory
char *create_string(char ch, int num) {
char *new_str = malloc(sizeof(char) * (num + 1));
for (int i = 0; i < num; i++) { main
argc: str: 0xed0
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str;
}

int main(int argc, char *argv[]) {

char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
'\0'
return 0;
Heap 'a'
}
'a'
'a'
'a'
57
0x0
 The Heap
Memory
char *create_string(char ch, int num) {
char *new_str = malloc(sizeof(char) * (num + 1));
for (int i = 0; i < num; i++) { main
argc: str: 0xed0
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str;
}

int main(int argc, char *argv[]) {

char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
'\0'
return 0;
Heap 'a'
}
'a'
'a'
'a'
58
0x0
 The Heap
Memory
char *create_string(char ch, int num) {
char *new_str = malloc(sizeof(char) * (num + 1));
for (int i = 0; i < num; i++) { main
argc: str: 0xed0
new_str[i] = ch; 1
Stack
} argv: 0xfff0
new_str[num] = '\0';
return new_str;
}

int main(int argc, char *argv[]) {

char *str = create_string('a', 4);
printf("%s", str); // want "aaaa"
'\0'
return 0;
Heap 'a'
}
'a'
'a'
'a'
59
0x0
 Exercise: malloc multiples
Let’s write a function that returns an array of the first len multiples of mult.
1 int *array_of_multiples(int mult, int len) {
2 /* TODO: arr declaration here */
3
4 for (int i = 0; i < len; i++) {
5 arr[i] = mult * (i + 1);
6 }
7 return arr;
8}
Line 2: How should we declare arr?
A. int arr[len];
B. int arr[] = malloc(sizeof(int));
C.
🤔
int *arr = malloc(sizeof(int) * len);
D. int *arr = malloc(sizeof(int) * (len + 1));
E. Something else 60
 Exercise: malloc multiples
Let’s write a function that returns an array of the first len multiples of mult.
1 int *array_of_multiples(int mult, int len) {
2 /* TODO: arr declaration here */
3
4 for (int i = 0; i < len; i++) {
5 arr[i] = mult * (i + 1);
6 } • Use a pointer to store the address
7 return arr; returned by malloc.
8} • Malloc’s argument is the number of
Line 2: How should we declare arr? bytes to allocate.
A. int arr[len]; ⚠ This code is missing an assertion.
B. int arr[] = malloc(sizeof(int));
C. int *arr = malloc(sizeof(int) * len);
D. int *arr = malloc(sizeof(int) * (len + 1));
E. Something else 61
 Always assert with the heap
Let’s write a function that returns an array of the first len multiples of mult.
1 int *array_of_multiples(int mult, int len) {
2 int *arr = malloc(sizeof(int) * len);
3 assert(arr != NULL);
4 for (int i = 0; i < len; i++) {
5 arr[i] = mult * (i + 1);
6 }
7 return arr;
8}

• If an allocation error occurs (e.g. out of heap memory!), malloc will return
NULL. This is an important case to check for robustness.
• assert will crash the program if the provided condition is false. A memory
allocation error is significant, and we should terminate the program.
62
 Other heap allocations: calloc
void *calloc(size_t nmemb, size_t size);
calloc is like malloc that zeros out the memory for you—thanks, calloc!

• You might notice its interface is also a little different—it takes two parameters,
which are multiplied to calculate the number of bytes (nmemb * size).
// allocate and zero 20 ints
int *scores = calloc(20, sizeof(int));
// alternate (but slower)
int *scores = malloc(20 * sizeof(int));
for (int i = 0; i < 20; i++) scores[i] = 0;
• calloc is more expensive than malloc because it zeros out memory. Use only
when necessary!
63
 Other heap allocations: strdup
char *strdup(char *s);
strdup is a convenience function that returns a null-terminated, heap-
allocated string with the provided text, instead of you having to malloc and
copy in the string yourself.

char *str = strdup("Hello, world!"); // on heap

str[0] = 'h';

64
 Cleaning Up with free
void free(void *ptr);
• If we allocated memory on the heap and no longer need it, it is our
responsibility to delete it.
• To do this, use the free command and pass in the starting address on the
heap for the memory you no longer need.
• Example:
char *bytes = malloc(4);
…
free(bytes);

65
 free details
Even if you have multiple pointers to the You must free the address you
same block of memory, each memory received in the previous allocation
block should only be freed once. call; you cannot free just part of a
previous allocation.

char *bytes = malloc(4); char *bytes = malloc(4);

char *ptr = bytes; char *ptr = malloc(10);
… …
free(bytes); ✅ free(bytes); ✅
… …
free(ptr); ❌ Memory at this free(ptr + 1); ❌
address was already
freed!
66
 Cleaning Up
You may need to free memory allocated by other functions if that function
expects the caller to handle memory cleanup.

char *str = strdup("Hello!");

…
free(str); // our responsibility to free!

67
 Memory Leaks
• A memory leak is when you allocate memory on the heap, but do not free it.
• Your program should be responsible for cleaning up any memory it allocates
but no longer needs.
• If you never free any memory and allocate an extremely large amount, you
may run out of memory in the heap!
However, memory leaks rarely (if ever) cause crashes.
• We recommend not to worry about freeing memory until your program is
written. Then, go back and free memory as appropriate.
• Valgrind is a very helpful tool for finding memory leaks!

68
 Lecture Plan
• The Stack
• The Heap and Dynamic Memory
• Practice: Pig Latin
• realloc
• Practice: Pig Latin Part 2

69
Demo: Pig Latin

pig_latin.c 70
 Lecture Plan
• The Stack
• The Heap and Dynamic Memory
• Practice: Pig Latin
• realloc
• Practice: Pig Latin Part 2

71
 realloc
void *realloc(void *ptr, size_t size);
• The realloc function takes an existing allocation pointer and enlarges to a new
requested size. It returns the new pointer.
• If there is enough space after the existing memory block on the heap for the
new size, realloc simply adds that space to the allocation.
• If there is not enough space, realloc moves the memory to a larger location,
frees the old memory for you, and returns a pointer to the new location.

72
 realloc
char *str = strdup("Hello");
assert(str != NULL);
…

// want to make str longer to hold "Hello world!"

char *addition = " world!";
str = realloc(str, strlen(str) + strlen(addition) + 1);
assert(str != NULL);

strcat(str, addition);
printf("%s", str);
free(str);

73
 realloc
• realloc only accepts pointers that were previously returned my malloc/etc.
• Make sure to not pass pointers to the middle of heap-allocated memory.
• Make sure to not pass pointers to stack memory.

74
 Cleaning Up with free and realloc
You only need to free the new memory coming out of realloc—the previous
(smaller) one was already reclaimed by realloc.
char *str = strdup("Hello");
assert(str != NULL);
…
// want to make str longer to hold "Hello world!"
char *addition = " world!";
str = realloc(str, strlen(str) + strlen(addition) + 1);
assert(str != NULL);
strcat(str, addition);
printf("%s", str);
free(str);

75
 Heap allocator analogy: A hotel
Request memory by size (malloc)
• Receive room key to first of connecting rooms
Need more room? (realloc)
• Extend into connecting room if available
• If not, trade for new digs, employee moves your
stuff for you
Check out when done (free)
• You remember your room number though
Errors! What happens if you…
• Forget to check out?
• Bust through connecting door to neighbor? What
if the room is in use? Yikes…
• Return to room after checkout?
76
 Lecture Plan
• The Stack
• The Heap and Dynamic Memory
• Practice: Pig Latin
• realloc
• Practice: Pig Latin Part 2

77
Demo: Pig Latin Part 2

pig_latin.c 78
 Heap allocation interface: A summary
void *malloc(size_t size);
void *calloc(size_t nmemb, size_t size);
void *realloc(void *ptr, size_t size);
char *strdup(char *s);
void free(void *ptr);

Compare and contrast the heap memory functions we’ve learned about.

🤔
79
 Heap allocation interface: A summary
void *malloc(size_t size);
void *calloc(size_t nmemb, size_t size);
void *realloc(void *ptr, size_t size);
char *strdup(char *s);
void free(void *ptr);
Heap memory allocation guarantee: Undefined behavior occurs:
• NULL on failure, so check with assert • If you overflow (i.e., you access
• Memory is contiguous; it is not recycled beyond bytes allocated)
unless you call free • If you use after free, or if free
• realloc preserves existing data is called twice on a location.
• calloc zero-initializes bytes, malloc • If you realloc/free non-heap
and realloc do not address
80
 Engineering principles: stack vs heap
Stack (“local variables”) Heap (dynamic memory)
• Fast
Fast to allocate/deallocate; okay to oversize
• Convenient.
Automatic allocation/ deallocation;
declare/initialize in one step
• Reasonable type safety
Thanks to the compiler
⚠ Not especially plentiful
Total stack size fixed, default 8MB
⚠ Somewhat inflexible
Cannot add/resize at runtime, scope
dictated by control flow in/out of functions
81
 Engineering principles: stack vs heap
Stack (“local variables”) Heap (dynamic memory)
• Fast • Plentiful.
Fast to allocate/deallocate; okay to oversize Can provide more memory on demand!
• Convenient. • Very flexible.
Automatic allocation/ deallocation; Runtime decisions about how much/when to
declare/initialize in one step allocate, can resize easily with realloc
• Reasonable type safety • Scope under programmer control
Thanks to the compiler Can precisely determine lifetime
⚠ Not especially plentiful ⚠ Lots of opportunity for error
Total stack size fixed, default 8MB Low type safety, forget to allocate/free
before done, allocate wrong size, etc.,
⚠ Somewhat inflexible Memory leaks (much less critical)
Cannot add/resize at runtime, scope
dictated by control flow in/out of functions
82
 Stack and Heap
• Generally, unless a situation requires dynamic allocation, stack allocation is
preferred. Often both techniques are used together in a program.
• Heap allocation is a necessity when:
• you have a very large allocation that could blow out the stack
• you need to control the memory lifetime, or memory must persist outside of a function
call
• you need to resize memory after its initial allocation

83
 Recap
• The Stack
• The Heap and Dynamic Memory
• Practice: Pig Latin
• realloc
• Practice: Pig Latin Part 2

Next time: C Generics

84
 Question Break
Post on Ed with any questions you have for today’s lecture!

85
Extra Practice

86
 Implementing strdup
How can we implement strdup using functions we’ve already seen?

char *myStrdup(char *str) {

char *heapStr = malloc(strlen(str) + 1);
assert(heapStr != NULL);
strcpy(heapStr, str);
return heapStr;
}

87
 Freeing Memory
Where should we free memory below so that all memory is freed properly?

1 char *str = strdup("Hello");

2 assert(str != NULL);
3 char *ptr = str + 1;
4 for (int i = 0; i < 5; i++) {
5 int *num = malloc(sizeof(int));
6 assert(num != NULL);
7 *num = i;
8 printf("%s %d\n", ptr, *num);
9 }
10 printf("%s\n", str);
88
 Freeing Memory
Where should we free memory below so that all memory is freed properly?

1 char *str = strdup("Hello");

2 assert(str != NULL);
3 char *ptr = str + 1;
4 for (int i = 0; i < 5; i++) {
5 int *num = malloc(sizeof(int));
6 assert(num != NULL);
7 *num = i;
8 printf("%s %d\n", ptr, *num);
9 free(num);
10 }
11 printf("%s\n", str);
12 free(str); 89