Carnegie Mellon

Memory Allocation
COMP 222: Introduction to Computer Organization

Instructor:
Alan L. Cox

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 1

 Objectives
 Be able to describe the differences between static
and dynamic memory allocation

 Be able to use malloc() and free() to manage

dynamically allocated memory in your programs

 Be able to analyze programs for memory

management related bugs

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 2

 Big Picture
 C gives you access to underlying data
representations & layout
 Needed for systems programming
 Potentially dangerous for application programming
 Necessary to understand
 Memory is a finite sequence of fixed-size storage
cells
 Most machines implement byte-sized storage cells

“byte-addresses”
 Individual bits are not addressable
 May also access multiple, aligned, contiguous storage cells as words, half-
words, quarter-words, etc.

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 3

 Structure Representation &
Size
sizeof(struct …) =
sum of sizeof(field) struct CharCharInt {
char c1;
+ alignment padding
Processor- and compiler-specific
char c2;
int i;
} foo;

foo.c1 = ’a’;
foo.c2 = ’b’;
foo.i = 0xDEADBEEF;

c1 c2 padding i

61 62 EF BE AD DE
x86 uses “little-endian” representation

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 4

 Pointer Arithmetic
pointer + number pointer – number

E.g., pointer + 1 adds 1 something to a pointer

char *p; int *p;

char a; int a;
char b; int b;

p = &a; p = &a;
p += 1; In each, p now points to b p += 1;
(Assuming compiler doesn’t
reorder variables in memory)

Adds 1*sizeof(char) to Adds 1*sizeof(int) to

the memory address the memory address

Pointer arithmetic should be used cautiously

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 5

 Can you tell if there is padding?
Yes! struct CharCharInt {
char c1;
char c2;
int i;
Print the } foo;

addresses of …(code from before)…

foo.c2 and printf(“&foo.c2 = %p\n”, &foo.c2);

foo.i printf(“&foo.i = %p\n”, &foo.i);

c1 c2 padding i

61 62 EF BE AD DE

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 6

 Can you access the padding?
struct CharCharInt {
Yes! char c1;
char c2;
int i;
} foo;

…(code from before)…

char *cp = &foo.c2;

cp += 1;
*cp = 0x7F;

c1 c2 padding i

61 62 7F EF BE AD DE
x86 uses “little-endian” representation

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 7

 Can you access both bytes?
Yes! struct CharCharInt {
char c1;
char c2;
int i;
} foo;

…(code from before)…

short *sp = (short *)(&foo.c2 + 1);

*sp = 0x7FFF;

c1 c2 padding i

61 62 FF 7F EF BE AD DE
x86 uses “little-endian” representation

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 8

 A Running Program’s Memory
0x7FFFFFFFFFFF
Unused

User Stack Created at runtime

47 bits of address space

Shared Libraries Shared among processes

Heap Created at runtime

Read/Write Data
Loaded from the executable
Read-only Code and Data

Unused
0x000000000000

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 9

 Allocation
 For all data, memory must be allocated
 Allocated = memory space reserved

 Two questions:
 When do we know the size to allocate?
 When do we allocate?
 Two possible answers for each:
 Compile-time (static)
 Run-time (dynamic)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 10

 How much memory to allocate?
 Sometimes obvious:

char c; One byte

int array[10];
10 * sizeof(int) (= 40 on CLEAR)

 Sometimes not:
Is this going to point to one
char *c; character or a string?
int *array;
How big will this array be?

 How will these be used???

 Will they point to already allocated memory (what we’ve seen so far)?
 Will new memory need to be allocated (we haven’t seen this yet)?

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 11

 malloc()
Won’t continually
remind you of this

#include <stdlib.h>

int *array = malloc(num_items * sizeof(int));

 Allocate memory dynamically

 Pass a size (number of bytes to allocate)
Finds unused memory that is large enough to hold the specified number

of bytes and reserves it
 Returns a void * that points to the allocated memory
 No typecast is needed for pointer assignment
 Essentially equivalent to new in Java

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 12

 Using malloc()
int *i; Statically or
dynamically
int *array;
allocates space for Dynamically
2 pointers allocates
i = malloc(sizeof(int)); space for
array = malloc(num_items * sizeof(int)); data

*i = 3;
array[3] = 5;

 i and array are interchangeable

 Arrays  pointers to the initial (0th) array element
 i could point to an array, as well
 May change over the course of the program
 Allocated memory is not initialized!
 calloc zeroes allocated memory (otherwise, same as malloc; details to
come in practice lab)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 13

 Using malloc()
 Always check the return value of library calls like malloc() for
errors
int *a = malloc(num_items * sizeof(int));
if (a == NULL) {
fprintf(stderr, “Out of memory.\n”);
exit(1);
}
Terminate now!
And, indicate error.
 For brevity, won’t in class
 Lab examples and provided code for assignments will
 Textbook uses capitalization convention
 Capitalized version of functions are wrappers that check for errors and exit if they occur
(i.e. Malloc)
 May not be appropriate to always exit on a malloc error, though, as you may be able to
recover memory

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 14

 When to Allocate?

 Static
Dynamic time time
 Typically
Typically global variables:
local variables:
int f(…)
{
int value;
int value;
int main(void)
…
{
}
…
int main(void)
}
{
…
}
 Only one copy ever exists, so can allocate at compile-time
 One copy exists for each call – may be unbounded # of calls, so can’t allocate at
compile-time

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 15

 When to Allocate?
 Static time
 Some local variables:
int f(…)
{
static int value;
…
One copy exists }
for all calls – int main(void)
allocated at {
compile-time
… Confusingly, local
} static has nothing to
do with global static!

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 16

 Allocation in Process Memory
0x7FFFFFFFFFFF

Stack Static size, dynamic allocation

Local variables

Shared Libraries

Programmer controlled
(variable-sized objects)
Heap Dynamic size, dynamic allocation

Read/Write Data Static size, static allocation

Read-only Code and Data Global variables

(and static local variables)

0x000000000000

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 17

 Why are there different
methods?
 Heap allocation is the most general
 Supports any size and number of allocations

 Why don’t we use it for everything?

 Performance

 Static allocation takes no run time

 Stack allocation takes orders of magnitude less run

time than heap allocation

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 18

 Deallocation
 Space allocated via variable definition (entering
scope) is automatically deallocated when exiting
scope
… f(void)
{
int y;
int array[10];
…
}

 Can’t refer to y or array outside of f(), so their space is deallocated

upon return

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 19

 Deallocation
 malloc() allocates memory explicitly
 Must also deallocate it explicitly (using free())!
 Not automatically deallocated (garbage collected) as in Python and Java
 Forgetting to deallocate leads to memory leaks & running out of memory

int *a = malloc(num_items * sizeof(int));

…
free(a);
…
a = malloc(2 * num_items * sizeof(int));

 Must not use a freed pointer unless reassigned or

reallocated

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 20

 Deallocation
 Space allocated by malloc() is freed when the
program terminates
 If data structure is used until program termination, don’t need to free
 Entire process’ memory is deallocated

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 21

 Back to create_date
Date * Date *
create_date3(int month, create_date3(int month,
int day, int year) int day, int year)
{ {
Date *d; Date *d;

d->month = month; d = malloc(sizeof(Date));

d->day = day; if (d != NULL) {
d->year = year; d->month = month;
d->day = day;
return (d); d->year = year;
} }

return (d);
}

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 22

 Pitfall
void
foo(void) Potential problem:
{ memory allocation is
Date *today; performed in this
function (may not know
today = create_date3(9, 20, 2024); its implementation)

/* Use “today”, if it is not NULL. */

...

return;
}

Memory is still allocated for

“today”!

Will never be deallocated (calling

function doesn’t even know
about it)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 23
 Possible Solutions
void void
foo(void) foo(void)
{ {
Date *today; Date *today;

today = create_date3(…); today = create_date3(…);

/* Use “today”, … */ /* Use “today”, … */

... ...

free(today); destroy_date(today);
return; return;
} }

Explicitly deallocate Complete the abstraction –

memory – specification of “create” has a corresponding
create_date3 must tell you “destroy”
to do this
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 24
 Scenario
 Suppose that we want to maintain a collection of
integers, but ...
 Over time, we will both add integers to and remove integers from the
collection
 And, we don't know the maximum size of the collection in advance

 We could use an array, but …

 For example, what happens when the size of the collection grows to the
point that it exceeds the array size?

 What are the alternatives?

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 25

 Linked List
 A linked list of integers has a naturally recursive
definition:
A linked list of integers is ...
 either empty, represented by NULL, or …
 non-empty, represented by a pointer to a struct with a first and a rest,
where …
 first is an integer and …
 rest is a pointer to a linked list
struct list {
int first;
struct list *rest;
};

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 26

 Make Non-Empty
struct list {
int first;
struct list *rest;
};

struct list *makeNE(int first, struct list *rest)

{
struct list *item = Malloc(sizeof(struct list));
item->first = first;
item->rest = rest;
return (item);
}

void foo(void)
{
struct list *list = makeNE(1, makeNE(2, makeNE(3, NULL)));
...

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 27

 What's Wrong With This
makeNE?
struct list {
int first;
struct list *rest;
};

struct list *makeNE(int first, struct list *rest)

{
struct list item;
item.first = first;
item.rest = rest;
return (&item);
}

void foo(void)
{
struct list *list = makeNE(1, makeNE(2, makeNE(3, NULL)));
...

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 28

 Visualization

list:

1 pad

2 pad

3 pad NULL

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 29

 Recursive Traversal
struct list {
int first;
struct list *rest;
};

void recur_print(struct list *list)

{
if (list == NULL) {
printf("NULL\n");
} else {
printf("%d, ", list->first);
recur_print(list->rest);
}
}

void foo(void)
{
struct list *list = makeNE(1, makeNE(2, makeNE(3, NULL)));
recur_print(list);
...

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 30

 Iterative Traversal
struct list {
int first;
struct list *rest;
};

void iter_print(struct list *list)

{
while (list != NULL) {
printf("%d, ", list->first);
list = list->rest;
}
printf("NULL\n");
}

void foo(void)
{
struct list *list = makeNE(1, makeNE(2, makeNE(3, NULL)));
iter_print(list);
...

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 31

 Iterative Append
struct list {
int first;
struct list *rest;
};

struct list *iter_append(struct list *list, int last_int)

{
struct list *last = makeNE(last_int, NULL);
if (list == NULL)
return (last);
struct list *curr = list;
while (curr->rest != NULL) // Find the last non-empty.
curr = curr->rest;
curr->rest = last;
return (list);
}

void foo(void)
{
struct list *list = makeNE(1, makeNE(2, makeNE(3, NULL)));
list = iter_append(list, 4);
...
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 32
 Removal
struct list {
int first;
struct list *rest;
};

void foo(void)
{
struct list *list = makeNE(1, makeNE(2, makeNE(3, NULL)));

// Remove 2 from the list:

struct list *two = list->rest;
list->rest = two->rest;
free(two);

...
}

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 33

 Assignment to two

list:

1 pad

2 pad

two:
3 pad NULL

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 34

 Assignment to list->rest

list:

1 pad

2 pad

two:
3 pad NULL

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 35

 free(two)

list:

1 pad

two:
3 pad NULL

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 36

 Common Memory Management Mistakes

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 37

 What’s Wrong With This Code?
int *f(…) int *make_array(…)
{ {
int i; int array[10];
… …
return (&i); return (array);
} }

 Consider the statement j = *f();

 Leads to referencing deallocated memory

 Never return a pointer to a local variable!

 Behavior depends on allocation pattern

 Space not reallocated (unlikely)  works
 Space reallocated  very unpredictable

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 38

 One Solution
int *f(…) int *make_array(…)
{ {
int *i_ptr = int *array =
malloc(sizeof(int)); malloc(10 * sizeof(int));
… …
return (i_ptr); return (array);
} }

 Allocate with malloc(), and return the pointer

 Upon return, space for local pointer variable is deallocated
 But the malloc-ed space isn’t deallocated until it is free-d
 Potential memory leak if caller is not careful, as with create_date3…

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 39

 What’s Wrong With This Code?
/* Return “y = Ax”. */
int *matvec(int **A, int *x) {
int *y = malloc(N * sizeof(int));
Initializatio int i, j;
n loop for
i=0y[] for (; i<N; i+=1)
j=0 for (; j<N; j+=1)
y[i] += A[i][j] * x[j];
return (y);
}

 malloc-ed & declared space is not initialized!

 i, j, y[i] initially contain unknown data – garbage
 Often has zero value, leading to seemingly correct results

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 40

 What’s Wrong With This Code?

char **p;
int i;

/* Allocate space for M*N matrix. */

p = malloc(M * sizeof(char)); char *

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

p[i] = malloc(N * sizeof(char));

 Allocates wrong amount of memory

 Leads to writing into either unallocated memory or memory allocated for
something else

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 41

 Explanation
Heap region in memory (each rectangle represents one byte)
Assume M = N = 2, a memory address is 8 bytes (or 64 bits)

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

`
p[i] = malloc(N * sizeof(char));

p[0]

p = malloc(M * sizeof(char));

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 42

 Corrected code
Heap region in memory (each rectangle represents one byte)
Assume M = N = 2, a memory address is 8 bytes (or 64 bits)
for (i = 0; i < M; i++)
p[i] = malloc(N * sizeof(char));

p[1]
`

p[0]

p = malloc(M * sizeof(char *));

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 43

 What’s Wrong With This Code?
char **p;
int i;

/* Allocate space for M*N matrix. */

< p = malloc(M * sizeof(char *));

for (i = 0; i <= M; i += 1)
p[i] = malloc(N * sizeof(char));

 Off-by-1 error
 Uses interval 0…M instead of 0…M-1
 Leads to writing unallocated memory

 Be careful with loop bounds!

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 44

 Using const with pointers
 const int *iptr
 Pointer to a constant integer
 Cannot write to *iptr

 int *const iptr

 Constant pointer to an integer
 Cannot modify the pointer (iptr)
 Can write to *iptr
char *
xyz(char * to, const char * from)
{
char *save = to;
for (; (*to = *from); ++from, ++to);
return(save);
}

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 45

 What’s Wrong With This Code?
char *s = “1234567”; char *
… strcpy(char * to, const char * from)
char t[7]; {
strcpy(t, s); char *save = to;
for (; (*to = *from); ++from, ++to);
return(save);
}

 t[] doesn’t have space for string terminator

 Leads to writing into unallocated memory
 One way to avoid:

char *s = “1234567”;
…
char *t = malloc((strlen(s) + 1) * sizeof(char));
strcpy(t, s);

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 46

 What’s Wrong With This Code?
/*
* Search memory for a value.
* Assume value is present.
*/
int *search(int *p, int value) {
while (*p > 0 && *p != value)
p += sizeof(int); p += 1;
return (p);
}

 Misused pointer arithmetic

 Search skips some data, can read unallocated memory, and might not
ever see value
 Should never add sizeof() to a pointer
 Could consider rewriting this function & its uses to use array notation
instead

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 47

 What’s Wrong With This Code?
x = malloc(N * sizeof(int));
…
free(x);
…
y = malloc(M * sizeof(int));
for (i = 0; i < M; i++) {
y[i] = x[i];
x[i] += 1;
}

 Premature free()
 Reads and writes deallocated memory

 Behavior depends on allocation pattern

 Space not reallocated  works
 Space reallocated  very unpredictable

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 48

 What’s Wrong With This Code?
void foo(void) {
int *x = malloc(N * sizeof(int));
…
free(x);
return;
}

 Memory leak – doesn’t free malloc-ed space

 Data still allocated, but inaccessible, since can’t refer to x

 Initially slows future memory performance and

may ultimately lead to failure

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 49

 What's Wrong With This Code?
struct list {
int first;
struct list *rest;
};

struct list *makeNE(int first, struct list *rest)

{
struct list *item = Malloc(sizeof(struct list));
item->first = first;
item->rest = rest;
return (item);
}

void foo(void)
{
struct list *list = makeNE(1, makeNE(2, makeNE(3, NULL)));
...
free(list);

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 50

 Example continued

Memory leak – frees only beginning of data structure

 Remainder of data structure is still allocated, but
inaccessible
 Need to write deallocation (destructor) routines for each
data structure

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 51

 Putting it all together ...
 bools
 strings

 pointers

 structs

 malloc() calls

 simple I/O

 simple string operations

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 52

 What does action1() do?
struct thing {
#include <stdio.h>
char *stuff;

struct thing *another_thing;

}; #include <stdlib.h>

void
#include <string.h>
action1(struct thing **yp, const char *stuff)

struct thing *x = malloc(sizeof(struct thing));

action1() inserts a new node storing the specified

/* Alternatively, x->stuff = strdup(stuff); */
string into the linked list
x->stuff = malloc(strlen(stuff) + 1);

strcpy(x->stuff, stuff);
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 53
 What does action2() do?
struct thing {

char *stuff;

struct thing *another_thing;

};

void

action2(struct thing **yp)

struct thing *x;

action2() prints the strings stored in the

while ((x = *yp) != NULL) {
linked list nodes sequentially
printf("%s ", x->stuff);

yp = &x->another_thing;
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 54
 What does action3() do?
struct thing {

char *stuff;

struct thing *another_thing;

};

bool

action3(struct thing **yp, const char *stuff)

struct thing *x;

while ((x = *yp) != NULL) {

action3() finds out whether a string

if (strcmp(x->stuff, stuff) == 0)

is stored in the linked list

return (true);

else

yp = &x->another_thing;
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 55
 What does action4() do?
struct thing {

char *stuff;

struct thing *another_thing;

};

void

action4(struct thing **yp, const char *stuff)

struct thing *x;

action4() deletes the first list node that

while ((x = *yp) != NULL) {
stores the specified string
if (strcmp(x->stuff, stuff) == 0) {

*yp = x->another_thing;
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 56