1 of 47

CSE 374 Programming Concepts and Tools

Lecture 10 - Memory Leaks

2 of 47

This week

Today

Monday: Dynamic Memory Allocation

Today: Memory Leaks

Friday: Debugging, GDB

Reviewing malloc and free

Memory Examples and Demos

Valgrind: Detecting memory leaks

3 of 47

Discussion

Turn and talk:

Should memory safety be the programmer’s responsibility or the language’s responsibility?

What are the tradeoffs between having the programmer manage memory directly versus relying on the language to enforce safety? In what kinds of situations might one approach be preferable over the other?

4 of 47

Review: malloc()

Usage:

Returns a void* to uninitialized heap memory

Returns NULL to indicate failure
Good practice to check result of malloc

Cast void* pointer to known type

Put the type you want to convert to in parentheses before the variable

sizeof() makes code portable to different machines

4

type* var = (type*) malloc(n * sizeof(type))

5 of 47

Review: free()

Usage:

Pointer must point to the first byte of heap-allocated memory

Undefined behavior (often program crash) otherwise
(Will do nothing if passed NULL)

Pointer is unaffected by call to free

Defensive programming: can set pointer to NULL after freeing it

Rule of thumb: for every call to malloc there should be one call to free

5

free(pointer);

6 of 47

Example: Heap and Stack

7 of 47

Initialized data

7

#include <stdlib.h>

int* copy(int a[], int size) {

int i, *a2;

a2 = (int*) malloc(size*sizeof(int));

if (a2 == NULL)

return NULL;

for (i = 0; i < size; i++)

a2[i] = a[i];

return a2;

}

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

int nums[4] = {1, 2, 3, 4};

int* ncopy = copy(nums, 4);

// .. do stuff with the array ..

free(ncopy);

return EXIT_SUCCESS;

}

OS kernel [protected]

Stack

Heap (malloc/free)

Globals

Code

main

ncopy

nums

Note: Arrow points to next line to run.

8 of 47

main local variables in stack

8

#include <stdlib.h>

int* copy(int a[], int size) {

int i, *a2;

a2 = (int*) malloc(size*sizeof(int));

if (a2 == NULL)

return NULL;

for (i = 0; i < size; i++)

a2[i] = a[i];

return a2;

}

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

int nums[4] = {1, 2, 3, 4};

int* ncopy = copy(nums, 4);

// .. do stuff with the array ..

free(ncopy);

return EXIT_SUCCESS;

}

OS kernel [protected]

Stack

Heap (malloc/free)

Globals

Code

main

ncopy

nums

1

2

3

4

9 of 47

copy local variables in stack

9

#include <stdlib.h>

int* copy(int a[], int size) {

int i, *a2;

a2 = (int*) malloc(size*sizeof(int));

if (a2 == NULL)

return NULL;

for (i = 0; i < size; i++)

a2[i] = a[i];

return a2;

}

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

int nums[4] = {1, 2, 3, 4};

int* ncopy = copy(nums, 4);

// .. do stuff with the array ..

free(ncopy);

return EXIT_SUCCESS;

}

OS kernel [protected]

Stack

Heap (malloc/free)

Globals

Code

main

ncopy

copy

a

size

4

nums

1

2

3

4

i

a2

10 of 47

malloc space for int array

10

#include <stdlib.h>

int* copy(int a[], int size) {

int i, *a2;

a2 = (int*) malloc(size*sizeof(int));

if (a2 == NULL)

return NULL;

for (i = 0; i < size; i++)

a2[i] = a[i];

return a2;

}

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

int nums[4] = {1, 2, 3, 4};

int* ncopy = copy(nums, 4);

// .. do stuff with the array ..

free(ncopy);

return EXIT_SUCCESS;

}

OS kernel [protected]

Stack

Heap (malloc/free)

Globals

Code

malloc

main

ncopy

copy

a

size

4

nums

1

2

3

4

i

a2

11 of 47

malloc space for int array

11

#include <stdlib.h>

int* copy(int a[], int size) {

int i, *a2;

a2 = (int*) malloc(size*sizeof(int));

if (a2 == NULL)

return NULL;

for (i = 0; i < size; i++)

a2[i] = a[i];

return a2;

}

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

int nums[4] = {1, 2, 3, 4};

int* ncopy = copy(nums, 4);

// .. do stuff with the array ..

free(ncopy);

return EXIT_SUCCESS;

}

OS kernel [protected]

Stack

Heap (malloc/free)

Globals

Code

main

ncopy

copy

a

size

4

nums

1

2

3

4

i

a2

12 of 47

Fill available space from local variables

12

#include <stdlib.h>

int* copy(int a[], int size) {

int i, *a2;

a2 = (int*) malloc(size*sizeof(int));

if (a2 == NULL)

return NULL;

for (i = 0; i < size; i++)

a2[i] = a[i];

return a2;

}

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

int nums[4] = {1, 2, 3, 4};

int* ncopy = copy(nums, 4);

// .. do stuff with the array ..

free(ncopy);

return EXIT_SUCCESS;

}

OS kernel [protected]

Stack

Heap (malloc/free)

Globals

Code

main

ncopy

copy

a

size

4

nums

1

2

3

4

i

0

a2

13 of 47

Fill available space from local variables

13

#include <stdlib.h>

int* copy(int a[], int size) {

int i, *a2;

a2 = (int*) malloc(size*sizeof(int));

if (a2 == NULL)

return NULL;

for (i = 0; i < size; i++)

a2[i] = a[i];

return a2;

}

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

int nums[4] = {1, 2, 3, 4};

int* ncopy = copy(nums, 4);

// .. do stuff with the array ..

free(ncopy);

return EXIT_SUCCESS;

}

OS kernel [protected]

Stack

Heap (malloc/free)

Globals

Code

1

2

3

4

main

ncopy

copy

a

size

4

nums

1

2

3

4

i

4

a2

14 of 47

Finish copy and free stack space

14

#include <stdlib.h>

int* copy(int a[], int size) {

int i, *a2;

a2 = (int*) malloc(size*sizeof(int));

if (a2 == NULL)

return NULL;

for (i = 0; i < size; i++)

a2[i] = a[i];

return a2;

}

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

int nums[4] = {1, 2, 3, 4};

int* ncopy = copy(nums, 4);

// .. do stuff with the array ..

free(ncopy);

return EXIT_SUCCESS;

}

OS kernel [protected]

Stack

Heap (malloc/free)

Globals

Code

1

2

3

4

main

ncopy

nums

1

2

3

4

15 of 47

Do stuff with the array…

15

#include <stdlib.h>

int* copy(int a[], int size) {

int i, *a2;

a2 = (int*) malloc(size*sizeof(int));

if (a2 == NULL)

return NULL;

for (i = 0; i < size; i++)

a2[i] = a[i];

return a2;

}

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

int nums[4] = {1, 2, 3, 4};

int* ncopy = copy(nums, 4);

// .. do stuff with the array ..

free(ncopy);

return EXIT_SUCCESS;

}

OS kernel [protected]

Stack

Heap (malloc/free)

Globals

Code

1

2

3

4

main

ncopy

nums

1

2

3

4

16 of 47

free ncopy from heap

16

#include <stdlib.h>

int* copy(int a[], int size) {

int i, *a2;

a2 = (int*) malloc(size*sizeof(int));

if (a2 == NULL)

return NULL;

for (i = 0; i < size; i++)

a2[i] = a[i];

return a2;

}

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

int nums[4] = {1, 2, 3, 4};

int* ncopy = copy(nums, 4);

// .. do stuff with the array ..

free(ncopy);

return EXIT_SUCCESS;

}

OS kernel [protected]

Stack

Heap (malloc/free)

Globals

Code

main

ncopy

nums

1

2

3

4

free

17 of 47

Exit

17

#include <stdlib.h>

int* copy(int a[], int size) {

int i, *a2;

a2 = (int*) malloc(size*sizeof(int));

if (a2 == NULL)

return NULL;

for (i = 0; i < size; i++)

a2[i] = a[i];

return a2;

}

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

int nums[4] = {1, 2, 3, 4};

int* ncopy = copy(nums, 4);

// .. do stuff with the array ..

free(ncopy);

return EXIT_SUCCESS;

}

OS kernel [protected]

Stack

Heap (malloc/free)

Globals

Code

main

ncopy

nums

1

2

3

4

18 of 47

Polling Time!

Please answer in the LP10 assignment on Gradescope!

Which line(s)�contain a memory error?

Select all that apply.

Line 7
Line 8
Line 9
Line 10
Line 11
Line 12

18

#include <stdlib.h>

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

int a[2];

int* b = (int*) malloc(2*sizeof(int));

a[2] = 5;

b[0] += 2;

free(&(a[0]));

free(b);

b[0] = 5;

return EXIT_SUCCESS;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

19 of 47

Demo: corrupt mem

19

20 of 47

Memory Errors

21 of 47

What is wrong here?

int x[] = {1, 2, 3};

free(x);

x is a local variable stored in stack, cannot be freed !

The free() function is used to deallocate memory that was previously allocated using dynamic memory allocation functions like malloc, calloc, or realloc.
The array x is declared as a regular array, not as a dynamically allocated array. It should not be freed using the free() function.

22 of 47

Common Memory Errors

Dereferencing a non-pointer
Accessing freed memory
Double free
Out-of-bounds access
Reading memory before initialization
Wrong allocation size
Forgetting to free memory ("memory leak")

22

23 of 47

Memory Leak

A memory leak occurs when code fails to deallocate dynamically-allocated memory that is no longer used

e.g. forgot to free malloc-ed block, lost/changed pointer to malloc-ed block

The Consequences: program’s memory will keep growing

This might be OK for short-lived program, since all memory is deallocated when program ends
Usually has bad repercussions for long-lived programs

Might slow down over time
Might exhaust all available memory and crash
Other programs might get starved of memory

23

24 of 47

Memory Leaks in Production

Memory leaks occur in reality all of the time.

End up looking like a sawtooth.

Developers need to resolve the issue, otherwise the system crashes.

Restart the server periodically (bad).
Use programming tools to discover and fix the issue (good).

24

25 of 47

Find the Bug!

26 of 47

Find That Bug! 🐞1

26

#define LEN 8

int arr[LEN];

for (int i = 0; i <= LEN; i++) {

arr[i] = 0;

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

Fix:

27 of 47

Improper bounds checking

27

#define LEN 8

int arr[LEN];

for (int i = 0; i <= LEN; i++) {

arr[i] = 0;

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

E

Fix: i < LEN

28 of 47

Find That Bug! 🐞2

28

int* foo() {

int val = 0;

return &val;

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

Fix:

29 of 47

Dangling pointer

29

int* foo() {

int val = 0;

return &val;

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

G

Fix: Allocate val dynamically (via malloc)

30 of 47

Find That Bug! 🐞3

30

// Create a matrix of N by M

int** p;

p = (int**)malloc(N * sizeof(int));

for (int i = 0; i < N; i++) {

p[i] = (int*)malloc(M * sizeof(int));

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

Fix:

31 of 47

Wrong allocation size

31

// Create a matrix of N by M

int** p;

p = (int**)malloc(N * sizeof(int));

for (int i = 0; i < N; i++) {

p[i] = (int*)malloc(M * sizeof(int));

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

H

Fix: N * sizeof(int*)

32 of 47

Find That Bug! 🐞4

32

int sum_int(int* arr, int len) {

int sum;

for (int i = 0; i < len; i++) {

sum += arr[i];

}

return sum;

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

Fix:

33 of 47

Invalid read

33

int sum_int(int* arr, int len) {

int sum;

for (int i = 0; i < len; i++) {

sum += arr[i];

}

return sum;

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

F

Fix: int sum = 0;

34 of 47

Aside: scanf

printf prints variables to stdout using format specifiers

scanf reads in values from stdin using format specifiers

You provide scanf a list of addresses to store the values in

int age;

printf("What is your age? ");

scanf("%d", &age);

printf("You are %d years old\n", age);

34

35 of 47

Demo: scanf

35

36 of 47

Find That Bug! 🐞5

The classic scanf bug

int scanf(const char* format, ...)

36

long val;

scanf("%ld", val);

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

Fix:

37 of 47

Dereferencing a non-pointer

The classic scanf bug

int scanf(const char* format, ...)

37

long val;

scanf("%ld", val);

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

A

Fix: &val

38 of 47

Find That Bug! 🐞6

38

x = (int*)malloc(N * sizeof(int));

… // manipulate x

free(x);

…

y = (int*)malloc(M * sizeof(int));

… // manipulate y

free(x);

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

Fix:

39 of 47

Double free

39

x = (int*)malloc(N * sizeof(int));

… // manipulate x

free(x);

…

y = (int*)malloc(M * sizeof(int));

… // manipulate y

free(x);

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

C

Fix: free(y)

40 of 47

Find That Bug! 🐞7

40

x = (int*)malloc(M * sizeof(int));

// manipulate x

free(x);

// ...

y = (int*)malloc(M * sizeof(int));

for (int i = 0; i < M; i++) {

y[i] = x[i];

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

Fix:

41 of 47

Accessing already freed memory

41

x = (int*)malloc(M * sizeof(int));

// manipulate x

free(x);

// ...

y = (int*)malloc(M * sizeof(int));

for (int i = 0; i < M; i++) {

y[i] = x[i];

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

B

Fix: move free(x) after for loop

42 of 47

Find That Bug! 🐞8

42

int foo() {

int* arr = (int*)malloc(sizeof(int) * N);

read_n_ints(N, arr);

int sum = 0;

for(int i = 0; i < N; i++) {

sum += arr[i];

}

return sum;

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

Fix:

43 of 47

Memory leak - failing to free memory

43

int foo() {

int* arr = (int*)malloc(sizeof(int) * N);

read_n_ints(N, arr);

int sum = 0;

for(int i = 0; i < N; i++) {

sum += arr[i];

}

return sum;

}

Dereferencing a non-pointer
Accessing already freed memory
Double free
Memory leak – failing to free memory
Improper/no bounds checking
Invalid read
Dangling pointer
Wrong allocation size

Error Type:

D

Fix: add free(arr) before returning

44 of 47

Finding and Fixing Memory Errors

Valgrind is a tool that simulates your program to find memory errors

It can detect all of the errors we just talked about! 😲

It catches pointer errors during execution, prints summary of heap usage, including details of memory leaks

valgrind [options] ./myprogram args args...

Useful option: –leak-check=full

Displays more detail about each memory leak

44

45 of 47

Valgrind Isn’t Perfect

Valgrind isn’t guaranteed to find all your memory problems.

Depends on what the program is doing while it’s running under valgrind.
If valgrind says no leaks are possible for a particular run, it can only guarantee that for a particular run.

For example, a memory leak might only manifest for a specific user input!

Always good to test with many different inputs

Rules out more bugs :)

More on testing in a couple of weeks!

45

46 of 47

Demo: Valgrind

46

47 of 47

Assignment Reminders

EX8 due Friday 7/18 @10:49am

EX8 will cover content from today and Wednesday’s lecture

HW3: Wordcount due this Friday 7/18 @11:59pm

Tips:

Please format messages exactly as they are shown in the examples for wordcount!

This includes choice of whitespace characters, capitalization, etc.

You can test the behavior of your wordcount implementation against wc

i.e., it should output the same numbers

Remember to put a newline at the end of files that you test wordcount on

Reminder: HW3 will have an associated Code Interview!

Make sure to submit LP10 before the next class as well.

All of these assignments can be found on our course's Gradescope page.