Roadmap
Memory Allocation I
CMPT 295
L22: Memory Allocation I
Roadmap
2
car *c = malloc(sizeof(car));
c->miles = 100;
c->gals = 17;
float mpg = get_mpg(c);
free(c);
Car c = new Car();
c.setMiles(100);
c.setGals(17);
float mpg =
c.getMPG();
Java:
C:
Assembly language:
Machine code:
0111010000011000
100011010000010000000010
1000100111000010
110000011111101000011111
Computer system:
OS:
Memory & data
Arrays & structs
Integers & floats
RISC V assembly
Procedures & stacks
Executables
Memory & caches
Processor Pipeline
Performance
Parallelism
CMPT 295
L22: Memory Allocation I
2
Multiple Ways to Store Program Data
Static global data
Fixed size at compile-time
Entire lifetime of the program
(loaded from executable)
Portion is read-only
(e.g. string literals)
Stack-allocated data
Local/temporary variables
Can be dynamically sized (in some versions of C)
Known lifetime (deallocated on return)
Dynamic (heap) data
Size known only at runtime (i.e. based on user-input)
Lifetime known only at runtime (long-lived data structures)
3
int array[1024];
void foo(int n) {
int tmp;
int local_array[n];
int* dyn =
(int*)malloc(n*sizeof(int));
}
CMPT 295
L22: Memory Allocation I
Memory Allocation
Dynamic memory allocation
Introduction and goals
Allocation and deallocation (free)
Fragmentation
Explicit allocation implementation
Implicit free lists
Explicit free lists (Lab 8)
Segregated free lists
Implicit deallocation: garbage collection
Common memory-related bugs in C
4
CMPT 295
L22: Memory Allocation I
Dynamic Memory Allocation
Programmers use dynamic memory allocators to acquire virtual memory at run time
For data structures whose size
(or lifetime) is known only at runtime
Manage the heap of a process’
virtual memory:
Types of allocators
Explicit allocator: programmer allocates and frees space
Example: malloc and free in C
Implicit allocator: programmer only allocates space (no free)
Example: garbage collection in Java, Caml, and Lisp
5
Program text (.text)
Initialized data (.data)
User stack
0
Heap (via malloc)
Uninitialized data (.bss)
CMPT 295
L22: Memory Allocation I
http://en.wikipedia.org/wiki/Data_segment#Program_memory
.data is for data that is initialized at compile-time: string literals, and static/global variables initialized to some value.
.bss is for static/global variables with no explicit initialization in the code.
http://en.wikipedia.org/wiki/.bss
.data is fixed-size, have to know ahead of time how much you need
Dynamic Memory Allocation
Allocator organizes heap as a collection of variable-sized blocks, which are either allocated or free
Allocator requests pages in the heap region; virtual memory hardware and OS kernel allocate these pages to the process
Application objects are typically smaller than pages, so the allocator manages blocks within pages
(Larger objects handled too;
ignored here)
6
Top of heap
(brk ptr)
Program text (.text)
Initialized data (.data)
User stack
0
Heap (via malloc)
Uninitialized data (.bss)
CMPT 295
L22: Memory Allocation I
Allocating Memory in C
Need to #include
void* malloc(size_t size)
Allocates a continuous block of size bytes of uninitialized memory
Returns a pointer to the beginning of the allocated block; NULL indicates failed request
Typically aligned to an 8-byte (x86) or 16-byte (x86-64) boundary
Returns NULL if allocation failed (also sets errno) or size==0
Different blocks not necessarily adjacent
Good practices:
ptr = (int*) malloc(n*sizeof(int));
sizeof makes code more portable
void* is implicitly cast into any pointer type; explicit typecast will help you catch coding errors when pointer types don’t match
7
CMPT 295
L22: Memory Allocation I
man 3 malloc
7
Allocating Memory in C
Need to #include
void* malloc(size_t size)
Allocates a continuous block of size bytes of uninitialized memory
Returns a pointer to the beginning of the allocated block; NULL indicates failed request
Typically aligned to an 8-byte (x86) or 16-byte (x86-64) boundary
Returns NULL if allocation failed (also sets errno) or size==0
Different blocks not necessarily adjacent
Related functions:
void* calloc(size_t nitems, size_t size)
“Zeros out” allocated block
void* realloc(void* ptr, size_t size)
Changes the size of a previously allocated block (if possible)
void* sbrk(intptr_t increment)
Used internally by allocators to grow or shrink the heap
8
CMPT 295
L22: Memory Allocation I
man 3 malloc
8
Freeing Memory in C
Need to #include
void free(void* p)
Releases whole block pointed to by p to the pool of available memory
Pointer p must be the address originally returned by m/c/realloc (i.e. beginning of the block), otherwise system exception raised
Don’t call free on a block that has already been released or on NULL
9
CMPT 295
L22: Memory Allocation I
man 3 free
9
Memory Allocation Example in C
10
void foo(int n, int m) {
int i, *p;
p = (int*) malloc(n*sizeof(int)); /* allocate block of n ints */
if (p == NULL) { /* check for allocation error */
perror(“malloc”);
exit(0);
}
for (i=0; i
When reading size, must remember to mask out this bit!
23
Format of
allocated and
free blocks:
a = 1: allocated block
a = 0: free block
size: block size (in bytes)
payload: application data
(allocated blocks only)
size
8 bytes
payload
a
optional
padding
e.g. with 8-byte alignment, possible values for size:
00001000 = 8 bytes
00010000 = 16 bytes
00011000 = 24 bytes
. . .
If x is first word (header):
x = size | a;
a = x & 1;
size = x & ~1;
size | a;
x & 1;
x & ~1;
CMPT 295
L22: Memory Allocation I
Where is p pointing?
/docProps/thumbnail.jpeg