MCIT 593 - Introduction to Computer Systems
Introduction to Computer Systems
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MCIT 593 - Introduction to Computer Systems
DYNAMIC MEMORY ALLOCATION
What Is Dynamic Memory Allocation?
• “Dynamic” means “at run-time” (not “at compile-time”)
• Compiler does not have enough information to make final decision
• Unlike “automatic” or “static” memory allocation, e.g.: int a = 0 ;
• Dynamic memory allocation example
• We would love to make arrays of dynamic length!
• Our dream in C:
int length = 2 ;
int int_array [length] ; /* why won’t this compile? */
• Remember in assembly…
• If you could just find a free spot in memory, you could write to it
• We have the same thing in C (except it is a bit safer)
What Is The Heap?
• 3 possible places to store data in C on the LC4:
• The Stack (known at compile time)
• local variables, arguments, returns
• The Global Region (known at compile time)
• static vars (global or local static)
• The heap (accessible at runtime)
• x4000-x6FFF
• This region is the topic of this module
Global Region
(static vars)
Stack
(automatic vars)
x0000
x3FFF
x4000
x6FFF
x7000
x7FFF
x1FFF
x2000
Heap
(dynamic vars)
Program Memory
User Data Memory
partitioned further for C:
globals, heap, stack
Heap API
• How does the programmer interface with “heap”?
• Two basic functions for heap: malloc() and free()
• Heap is managed by user-level C runtime library (libc)
• Interface function declarations found in stdlib.h
void* malloc(size_t size) ;
• Returns a pointer to a region on the heap of size size bytes
• If success, space is contiguous
• Recall that size_t is simply an typedef’d unsigned int
• Returns NULL if heap can’t fulfill request
• Recall that void* is “generic pointer” (C for “just an address”)
• Can pass it around, but not dereference
• Analogous to making a “reservation” for dinner – secures reservation, up to you to use!
Heap API
• How does the programmer interface with “heap”?
• Two basic functions for heap: malloc() and free()
• Heap is managed by user-level C runtime library (libc)
• Interface function declarations found in stdlib.h
void* malloc(size_t size) ;
• Returns a pointer to a region on the heap of size size bytes
• If success, space is contiguous
• If failure, returns NULL
• Analogous to making a “reservation” for dinner – secures reservation, up to you to use!
void free(void* ptr) ;
• Clears reservation for address pointed to be ptr
• The memory region pointed to by ptr, was previously given to you by malloc()
HEAP API EXAMPLE 1: CREATING ARRAY
AT RUNTIME
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * 4); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
Why can’t we do this?
pointer points
to nothing RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
stack memory
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * 4); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
x4000
Xx4000 int_array[0]
Xx4001
heap memory
int_array[1]
stack memory
Why can we do this now?
we have two spots
on the heap!
1
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * 4); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
x4000
Xx4000 int_array[0]
Xx4001
heap memory
int_array[1]
free() doesn’t actually modify *int_array or clear the heap!
stack memory
1
0
17Instead it releases your “reservation” on address x4000 for 8 bytes
Property of Penn Engineering
MCIT 593 - Introduction to Computer Systems
Heap API Example 1: Creating An “Array” At Runtime
#include
int main () {
int* int_array ;
/* request memory allocation from heap */
int_array = malloc(2 * ); /* 8 bytes */
/* make certain malloc succeeded */
if (int_array == NULL) return 1 ;
/* populate array */
int_array[0] = 0 ;
int_array[1] = 1 ;
/* return allocated memory
back to heap */
free(int_array);
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
*int_array
FPx7FFC
x4000
Xx4000 int_array[0]
Xx4001
heap memory
int_array[1]
sizeof() is actually an operator in C (not a function)
stack memory
1
0
18It can compute the size of its operand…works on any datatype…even structs!
sizeof(int)
MCIT 593 - Introduction to Computer Systems
HEAP API EXAMPLE 2: RETURNING
ARRAY FROM FUNCTION
MCIT 593 - Introduction to Computer Systems
21
Heap API Example 2: Returning An “Array” From Function!
#include
int* create_array (int length) {
int* array = NULL ;
array = malloc (length * sizeof(int)) ;
return (array) ;
}
int main () {
int len = 2 ;
int* int_array = NULL ;
int_array = create_array(len) ;
if (int_array == NULL) return 1 ;
int_array[0]=0 ; // data is in heap!
int_array[1]=1 ;
free(int_array);
return 0 ;
} We are not returning a local variable’s address
Instead we are returning an address on the heap
RA
argsx7FFF
x7FFD
x7FFE RV
2x7FFB
R5
len
FPx7FFC
0x4006 int_array[0]
1x4007
heap memory
int_array[1]
NULLx7FFA *int_array
2
Xx7FF8
x7FF9
x7FF7 X
RV
length
RA
x7FF6 x7FFC FP
x7FF5 NULL *array
R5
x4006
x4006
x4006
Heap API Example 3:
Strings (Global/Stack/Heap)
#include
char str_global[3] ;
int main () {
char* str_readonly = “Hi” ;
char str_stack[3] ;
char* str_heap ;
malloc (strlen(str_readonly)+1) ;
strcpy (str_global, str_readonly) ;
strcpy (str_stack, str_readonly) ;
strcpy (str_heap, str_readonly) ;
free(str_heap);
return 0 ;
} How long does heap memory last?
Until you free it!
Does it actually clear?
Does *str_heap change?
The other types are governed by compiler
RA
argsx7FFE
x7FFC
x7FFD RV
x200Dx7FFA
R5
*str_readonly
FPx7FFB
‘\0’x200C str_global[2]
‘H’x200D
Global/static Memory
‘\0’x7FF9 str_stack[2]
‘i’
‘H’str_stack
x7FF8
x7FF6 x4000
str_stack[0]
str_stack[1]
‘H’str_global str_global[0]
‘i’x200B str_global[1]
*str_heap
‘H’x4000 str_heap[0]
‘i’x4001 str_heap[1]
‘i’x200E str_readonly[1]
‘\0’x200F str_readonly[2]
‘\0’x4002 str_heap[2]
Heap Memory
Stack Memory
str_readonly[0]
=
24
Property of Penn Engineering
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char name [4] ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
strcpy (my_cust.name, “Tom”) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name[3]
FPx7FFC
‘m’x7FFA my_cust.name[2]
X
Xx7FF8
x7FF9
x7FF7 X
my_cust.name[0]
my_cust.name[1]
my_cust.id
All data in this example lives on the stack!
stack memory
X
‘T’
‘o’
‘\0’
1234
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
strcpy (my_cust.name, “Tom”) ;
return 0 ;
}
RA
argsx7FFF
x7FFD
x7FFE RV
Xx7FFB
R5
my_cust.name[3]
FPx7FFC
Xx7FFA my_cust.name[2]
X
Xx7FF8
x7FF9
x7FF7 X
my_cust.name[0]
my_cust.name[1]
my_cust.id
What if we made this change?
Could I still do this? stack memory
‘T’
‘o’
‘\0’
1234
‘m’
MCIT 593 - Introduction to Computer Systems
29
Heap API Example 4: Structures on the Stack / Heap
#include
typedef struct cust_struct {
int id ;
char* name ;
} customer ;
int main () {
customer my_cust ; // allocate my_cust on stack
my_cust.id = 1234 ;
strcpy (my_cust.name, “Tom”) ;