Dynamic Memory Allocation Strategies in CS
CS 105
Lecture 12: Dynamic Memory (cont'd)
Dynamic Memory Allocation Goals
2
•
Provide memory (in heap) to a running program (allocate)
•
Recycle memory when done (free)
•
H
i
g
h
t
h
r
o
u
g
h
p
u
t
:
n
u
m
b
e
r
o
f
r
e
q
u
e
s
t
s
c
o
m
p
l
e
t
e
d
p
e
r
t
i
m
e
u
n
i
t
•
Make allocator efficient
•
E
x
a
m
p
l
e
:
i
f
y
o
u
r
a
l
l
o
c
a
t
o
r
p
r
o
c
e
s
s
e
s
5
,
0
0
0
m
a
l
l
o
c
c
a
l
l
s
a
n
d
5
,
0
0
0
f
r
e
e
c
a
l
l
s
i
n
1
0
s
e
c
o
n
d
s
t
h
e
n
t
h
r
o
u
g
h
p
u
t
i
s
1
,
0
0
0
o
p
e
r
a
t
i
o
n
s
/
s
e
c
o
n
d
•
H
i
g
h
m
e
m
o
r
y
u
t
i
l
i
z
a
t
i
o
n
:
f
r
a
c
t
i
o
n
o
f
h
e
a
p
m
e
m
o
r
y
a
l
l
o
c
a
t
e
d
•
Minimize fragmentation
Challenges
•
Goal: maximize throughput and peak memory utilization
•
Implementation Challenges:
•
How do we know how much memory to free given just a pointer?
•
How do we keep track of the free blocks?
•
How do we pick a block to use for allocation?
•
What do we do with the extra space when allocating a structure
that is smaller than the free block it is placed in?
•
How do we reinsert a freed block?
3
Summary of Key Allocator Policies
•
Free-block storage policy:
•
Implicit lists, with boundary tags (nice and simple)
•
Explicit lists, exclude free blocks (faster, but more overhead)
•
Segregated lists (different lists for different sized blocks)
•
Fancy data structures (red-black trees, for example)
•
Placement policy:
•
First-fit (simple, but lower throughput and higher fragmentation)
•
Next-fit (higher throughput, higher fragmentation)
•
Best-fit (lower throughput, lower fragmentation
•
segregated free lists approximate a best fit placement policy without having to
search entire free list
•
Splitting policy:
•
When do we go ahead and split free blocks?
•
How much internal fragmentation are we willing to tolerate?
4
Challenges
•
Goal: maximize throughput and peak memory utilization
•
Implementation Challenges:
•
How do we know how much memory to free given just a pointer?
•
How do we keep track of the free blocks?
•
How do we pick a block to use for allocation?
•
What do we do with the extra space when allocating a structure
that is smaller than the free block it is placed in?
•
How do we reinsert a freed block?
5
Implicit List: Freeing a Block
•
Simplest implementation:
•
Need only clear the “allocated” flag
void free_block(ptr p) { *p = *p & -2 }•
But can lead to “false fragmentation”
6
There is enough free space, but the allocator won’t be able to find it
Implicit List: Coalescing
•
Join
(coalesce)
with next/previous blocks, if they are free
•
Coalescing with next block
•
But how do we coalesce with
previous
block?
7
void free_block(ptr p) {*p = *p & -2;
// clear allocated flag
next = p + *p;
// find next block
if ((*next & 1) == 0)
*p = *p + *next;
// add to this block if
}
// not allocated
17
9
17
8
free(p)
p
16
17
9
16
24
8
logically
gone
Implicit List: Bidirectional Coalescing
•
B
o
u
n
d
a
r
y
t
a
g
s
[
K
n
u
t
h
7
3
]
•
Replicate size/allocated word at “bottom” (end) of free blocks
•
Allows us to traverse the “list” backwards, but requires extra space
•
Important and general technique!
8
S
ize
Format of
allocated and
free blocks
P
ayload and
padding
a = 1: Allocated block
a = 0: Free block
S
ize: Total block size
P
ayload: Application data
(allocated blocks only)
a
S
ize
a
Boundary tag
(footer)
Header
Constant-Time Coalescing
Case 2: Block above allocated, block below free
Case 1: Blocks above and below allocated
Case 2: Block above free, block below allocated
Case 4: Blocks above and below free
0x00000018
0x00000018
Exercise 1: Coalescing
•
Assume the current state of the heap is shown below.
What would be the state of the heap after the function
free(0x114)
is executed?
0x00000009
0x5ca1ab1e
0x00000011
0x0000000d
0xdeadcafe
0x0000000d
0x0000000c
0x00000047
0x00000011
0x100
0x104
0x108
0x10c
0x110
0x114
0x118
0x11c
0x120
0x124
previous block (allocated)
current block (allocated)
following block (free)
0x0000000c
Summary of Key Allocator Policies
•
Storage policy:
•
what data structure will you use to keep track of the free blocks?
•
Placement policy:
•
First-fit, next-fit, best-fit, etc.
•
Trades off lower throughput for less fragmentation
•
segregated free lists approximate a best fit placement policy without
having to search entire free list
•
Splitting policy:
•
When do we go ahead and split free blocks?
•
How much internal fragmentation are we willing to tolerate?
•
Coalescing policy:
•
I
m
m
e
d
i
a
t
e
c
o
a
l
e
s
c
i
n
g
:
c
o
a
l
e
s
c
e
e
a
c
h
t
i
m
e
f
r
e
e
i
s
c
a
l
l
e
d
•
D
e
f
e
r
r
e
d
c
o
a
l
e
s
c
i
n
g
:
t
r
y
t
o
i
m
p
r
o
v
e
p
e
r
f
o
r
m
a
n
c
e
o
f
f
r
e
e
b
y
d
e
f
e
r
r
i
n
g
c
o
a
l
e
s
c
i
n
g
u
n
t
i
l
n
e
e
d
e
d
.
E
x
a
m
p
l
e
s
:
•
C
o
a
l
e
s
c
e
a
s
y
o
u
s
c
a
n
t
h
e
f
r
e
e
l
i
s
t
f
o
r
m
a
l
l
o
c
•
Coalesce when the amount of external fragmentation reaches some
threshold
11
11
Memory-Related Perils and Pitfalls
•
Dereferencing bad pointers
•
Reading uninitialized memory
•
Overreading memory
•
Overwriting memory
•
Referencing freed blocks
•
Freeing blocks multiple times
•
Failing to free blocks
12
12
(Performance)
Tools for Dealing With Memory Bugs
•
Debugger:
gdb
•
Good for finding bad pointer dereferences
•
Hard to detect the other memory bugs
•
Heap consistency checker (e.g.,
mcheck
)
•
Usually run silently, printing message only on error
•
Can be used to detect overreads, double-free
•
glibc malloc contains checking code
•
setenv MALLOC_CHECK_ 3
•
B
i
n
a
r
y
t
r
a
n
s
l
a
t
o
r
:
v
a
l
g
r
i
n
d
•
Powerful debugging and analysis technique
•
Rewrites text section of executable object file
•
Checks each individual reference at runtime
•
Bad pointers, overwrites, refs outside of allocated block
13
13
But Memory Bugs Persist…
Implicit Allocators: Garbage Collection
•
G
a
r
b
a
g
e
c
o
l
l
e
c
t
i
o
n
:
a
u
t
o
m
a
t
i
c
r
e
c
l
a
m
a
t
i
o
n
o
f
h
e
a
p
-
a
l
l
o
c
a
t
e
d
s
t
o
r
a
g
e
—
a
p
p
l
i
c
a
t
i
o
n
n
e
v
e
r
h
a
s
t
o
f
r
e
e
•
Common in many dynamic languages:
•
Python, Java, Ruby, Perl, ML, Lisp, Mathematica
•
Variants (“conservative” garbage collectors) exist for C
and C++
•
However, cannot necessarily collect all garbage
void foo() {int *p = malloc(128);
return; /* p block is now garbage */
}
Garbage Collection
•
How does the memory manager know when memory can
be freed?
•
In general we cannot know what is going to be used in the future
since it depends on conditionals
•
But we can tell that certain blocks cannot be used if there are no
pointers to them
•
Must make certain assumptions about pointers
•
Memory manager can distinguish pointers from non-pointers
•
All pointers point to the start of a block
•
Cannot hide pointers
(e.g., by coercing them to an
long
, and then back again)
Memory as a Graph
•
We view memory as a directed graph
•
E
a
c
h
b
l
o
c
k
i
s
a
n
o
d
e
i
n
t
h
e
g
r
a
p
h
(
c
a
l
l
e
d
a
h
e
a
p
n
o
d
e
)
•
E
x
t
r
a
r
o
o
t
n
o
d
e
s
c
o
r
r
e
s
p
o
n
d
t
o
l
o
c
a
t
i
o
n
s
n
o
t
i
n
t
h
e
h
e
a
p
t
h
a
t
c
o
n
t
a
i
n
p
o
i
n
t
e
r
s
i
n
t
o
t
h
e
h
e
a
p
•
registers, local stack variables, or global variables
•
Each pointer is an edge in the graph
Root nodes
Heap nodes
Memory as a Graph
•
A node n is reachable if there exists a directed path from
some root node to n
•
Heap nodes that are not reachable are garbage
•
they can never again be used by the application
•
they should be freed ("garbage collected")Root nodes
Heap nodes
Garbage Collection
•
The role of a garbage collector is
1.
to maintain some representation of the reachability graph
2.
to reclaim the unreachable nodes by freeing them
•
this can happen periodically or collector can run in parallel with
application)
Languages that maintain tight control over how applications
create and use pointers (e.g., Java, Python, OCaml) can
maintain an exact representation of the graph
Garbage collectors for languages like C/C++ will be
conservative
Heap nodes
Exercise 2: Garbage Collection
•
Consider the following graph representation of memory.
Which nodes correspond to blocks that should be freed by
the garbage collector?
A
B
C
D
E
G
H
J
K
F
I
Root nodes
Classical GC Algorithms
•
Mark-and-sweep collection (McCarthy, 1960)
•
Does not move blocks (unless you also “compact”)
•
Reference counting (Collins, 1960)
•
Does not move blocks
•
Copying collection (Minsky, 1963)
•
Moves blocks
•
Generational Collectors (Lieberman and Hewitt, 1983)
•
Collection based on lifetimes
•
Most allocations become garbage very soon
•
So focus reclamation work on zones of memory recently allocated
Mark and Sweep Collector
•
E
a
c
h
b
l
o
c
k
h
e
a
d
e
r
h
a
s
a
n
e
x
t
r
a
m
a
r
k
b
i
t
•
can use one of the spare low-order bits
•
Two
phase protocol
•
M
a
r
k
:
S
t
a
r
t
a
t
r
o
o
t
s
a
n
d
s
e
t
m
a
r
k
b
i
t
o
n
e
a
c
h
r
e
a
c
h
a
b
l
e
b
l
o
c
k
•
S
w
e
e
p
:
S
c
a
n
a
l
l
b
l
o
c
k
s
a
n
d
f
r
e
e
b
l
o
c
k
s
t
h
a
t
a
r
e
n
o
t
m
a
r
k
e
d
Mark and Sweep Collector
ptr mark(ptr p) {if (!is_ptr(p)) return; // do nothing if not pointer
if (markBitSet(p)) return; // check if already marked
setMarkBit(p); // set the mark bit
for (i=0; i < length(p); i++) // call mark on all words
mark(p[i]);
// in the block
return;
}
Mark using depth-first traversal of the memory graph
Sweep using lengths to find next block
ptr sweep(ptr p, ptr end) { while (p < end) {if markBitSet(p)
clearMarkBit();
else if (allocateBitSet(p))
free(p);
p += length(p);
}
Conservative Mark & Sweep in C
•
A “conservative garbage collector” for C programs
•
build on top of malloc/free package
•
allocate using
malloc
until you “run out of space”
•
i
s
_
p
t
r
(
)
d
e
t
e
r
m
i
n
e
s
i
f
a
w
o
r
d
i
s
a
p
o
i
n
t
e
r
b
y
c
h
e
c
k
i
n
g
i
f
i
t
p
o
i
n
t
s
t
o
a
n
a
l
l
o
c
a
t
e
d
b
l
o
c
k
o
f
m
e
m
o
r
y
•
But, in C pointers can point to the middle of a block
•
So how to find the beginning of the block?
•
Can use a balanced binary tree to keep track of all allocated blocks
(key is start-of-block)
•
Balanced-tree pointers can be stored in header (use two additional
words)
Header
ptr
Head
D
ata
L
eft
R
ight
S
ize
Left:
smaller addresses
Right:
larger addresses
Exercise 3: Garbage Collection in C
•
Mark and Sweep garbage collectors are called conservative
if:
a)
They coalesce freed memory blocks during the sweep phase
b)
They treat everything that looks like a valid pointer as a pointer
c)
They perform garbage collection only when they run out of memory
d)
They do not free memory blocks forming a cyclic list
Exercise 4: Feedback
1.
Rate how well you think this recorded lecture worked
1.
Better than an in-person class
2.
About as well as an in-person class
3.
Less well than an in-person class, but you still learned something
4.
Total waste of time, you didn't learn anything
2.
How much time did you spend on this video (including
exercises)?
3.
Do you have any particular questions you’d like me to
address in this week’s problem session?
4.
Do you have any other comments or feedback?
Dynamic memory allocation in CS aims to efficiently provide and recycle memory in the heap for running programs. Key goals include high throughput and memory utilization while minimizing fragmentation. Challenges involve determining how much memory to free, tracking free blocks, selecting blocks for allocation, managing extra space, and reinserting freed blocks. Various allocator policies like free-block storage, placement, and splitting policies are used to optimize memory management.
Uploaded on Sep 25, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
2 Dynamic Memory Allocation Goals Provide memory (in heap) to a running program (allocate) Recycle memory when done (free) High throughput: number of requests completed per time unit Make allocator efficient Example: if your allocator processes 5,000 malloc calls and 5,000 freecalls in 10 seconds then throughput is 1,000 operations/second High memory utilization: fraction of heap memory allocated Minimize fragmentation
3 Challenges Goal: maximize throughput and peak memory utilization Implementation Challenges: How do we know how much memory to free given just a pointer? How do we keep track of the free blocks? How do we pick a block to use for allocation? What do we do with the extra space when allocating a structure that is smaller than the free block it is placed in? How do we reinsert a freed block?
4 Summary of Key Allocator Policies Free-block storage policy: Implicit lists, with boundary tags (nice and simple) Explicit lists, exclude free blocks (faster, but more overhead) Segregated lists (different lists for different sized blocks) Fancy data structures (red-black trees, for example) Placement policy: First-fit (simple, but lower throughput and higher fragmentation) Next-fit (higher throughput, higher fragmentation) Best-fit (lower throughput, lower fragmentation segregated free lists approximate a best fit placement policy without having to search entire free list Splitting policy: When do we go ahead and split free blocks? How much internal fragmentation are we willing to tolerate?
5 Challenges Goal: maximize throughput and peak memory utilization Implementation Challenges: How do we know how much memory to free given just a pointer? How do we keep track of the free blocks? How do we pick a block to use for allocation? What do we do with the extra space when allocating a structure that is smaller than the free block it is placed in? How do we reinsert a freed block?
6 Implicit List: Freeing a Block Simplest implementation: Need only clear the allocated flag void free_block(ptr p) { *p = *p & -2 } But can lead to false fragmentation 16 17 17 9 8 p free(p) 16 17 16 9 8 malloc(20)Oops! There is enough free space, but the allocator won t be able to find it
7 Implicit List: Coalescing Join (coalesce) with next/previous blocks, if they are free Coalescing with next block 16 17 17 9 8 logically gone p free(p) 16 17 24 9 8 void free_block(ptr p) { *p = *p & -2; // clear allocated flag next = p + *p; // find next block if ((*next & 1) == 0) *p = *p + *next; // add to this block if } // not allocated But how do we coalesce with previous block?
8 Implicit List: Bidirectional Coalescing Boundary tags[Knuth73] Replicate size/allocated word at bottom (end) of free blocks Allows us to traverse the list backwards, but requires extra space Important and general technique! 16 16 17 17 24 24 17 17 a = 1: Allocated block a = 0: Free block Header Size a Format of allocated and free blocks Size: Total block size Payload and padding Payload: Application data (allocated blocks only) Boundary tag (footer) Size a
Constant-Time Coalescing Case 2: Block above allocated, block below free Case 1: Blocks above and below allocated Case 2: Block above free, block below allocated Case 4: Blocks above and below free
Exercise 1: Coalescing Assume the current state of the heap is shown below. What would be the state of the heap after the function free(0x114) is executed? 0x00000018 0x0000000c 0x124 0x00000047 following block (free) 0x120 0x0000000c 0x11c 0x0000000d 0x118 current block (allocated) 0xdeadcafe 0x114 0x00000018 0x0000000d 0x110 0x00000011 0x10c 0x5ca1ab1e previous block (allocated) 0x108 0x00000009 0x104 0x00000011 0x100
11 Summary of Key Allocator Policies Storage policy: what data structure will you use to keep track of the free blocks? Placement policy: First-fit, next-fit, best-fit, etc. Trades off lower throughput for less fragmentation segregated free lists approximate a best fit placement policy without having to search entire free list Splitting policy: When do we go ahead and split free blocks? How much internal fragmentation are we willing to tolerate? Coalescing policy: Immediate coalescing: coalesce each time freeis called Deferred coalescing: try to improve performance of freeby deferring coalescing until needed. Examples: Coalesce as you scan the free list for malloc Coalesce when the amount of external fragmentation reaches some threshold
12 Memory-Related Perils and Pitfalls (Correctness) Dereferencing bad pointers (Correctness) Reading uninitialized memory Overreading memory (Security) (Security) Overwriting memory (Security) Referencing freed blocks (Security) Freeing blocks multiple times (Performance) Failing to free blocks
13 Tools for Dealing With Memory Bugs Debugger: gdb Good for finding bad pointer dereferences Hard to detect the other memory bugs Heap consistency checker (e.g., mcheck) Usually run silently, printing message only on error Can be used to detect overreads, double-free glibc malloc contains checking code setenv MALLOC_CHECK_ 3 Binary translator: valgrind Powerful debugging and analysis technique Rewrites text section of executable object file Checks each individual reference at runtime Bad pointers, overwrites, refs outside of allocated block
Implicit Allocators: Garbage Collection Garbage collection: automatic reclamation of heap- allocated storage application never has to free void foo() { int *p = malloc(128); return; /* p block is now garbage */ } Common in many dynamic languages: Python, Java, Ruby, Perl, ML, Lisp, Mathematica Variants ( conservative garbage collectors) exist for C and C++ However, cannot necessarily collect all garbage
Garbage Collection How does the memory manager know when memory can be freed? In general we cannot know what is going to be used in the future since it depends on conditionals But we can tell that certain blocks cannot be used if there are no pointers to them Must make certain assumptions about pointers Memory manager can distinguish pointers from non-pointers All pointers point to the start of a block Cannot hide pointers (e.g., by coercing them to an long, and then back again)
Memory as a Graph We view memory as a directed graph Each block is a node in the graph (called a heap node) Extra root nodes correspond to locations not in the heap that contain pointers into the heap registers, local stack variables, or global variables Each pointer is an edge in the graph Root nodes Heap nodes
Memory as a Graph A node n is reachable if there exists a directed path from some root node to n Heap nodes that are not reachable are garbage they can never again be used by the application they should be freed ("garbage collected") Root nodes reachable Heap nodes Not-reachable (garbage)
Garbage Collection The role of a garbage collector is to maintain some representation of the reachability graph to reclaim the unreachable nodes by freeing them this can happen periodically or collector can run in parallel with application) 1. 2. Languages that maintain tight control over how applications create and use pointers (e.g., Java, Python, OCaml) can maintain an exact representation of the graph Garbage collectors for languages like C/C++ will be conservative
Exercise 2: Garbage Collection Consider the following graph representation of memory. Which nodes correspond to blocks that should be freed by the garbage collector? B A Root nodes F C D E Heap nodes K J G H I
Classical GC Algorithms Mark-and-sweep collection (McCarthy, 1960) Does not move blocks (unless you also compact ) Reference counting (Collins, 1960) Does not move blocks Copying collection (Minsky, 1963) Moves blocks Generational Collectors (Lieberman and Hewitt, 1983) Collection based on lifetimes Most allocations become garbage very soon So focus reclamation work on zones of memory recently allocated
Mark and Sweep Collector Each block header has an extra mark bit can use one of the spare low-order bits Two phase protocol Mark: Start at roots and set mark bit on each reachable block Sweep: Scan all blocks and free blocks that are not marked root Note: arrows here denote memory refs, not free list ptrs. Before mark After mark Mark bit set After sweep free free
Mark and Sweep Collector Mark using depth-first traversal of the memory graph ptr mark(ptr p) { if (!is_ptr(p)) return; // do nothing if not pointer if (markBitSet(p)) return; // check if already marked setMarkBit(p); // set the mark bit for (i=0; i < length(p); i++) // call mark on all words mark(p[i]); // in the block return; } Sweep using lengths to find next block ptr sweep(ptr p, ptr end) { while (p < end) { if markBitSet(p) clearMarkBit(); else if (allocateBitSet(p)) free(p); p += length(p); }
Conservative Mark & Sweep in C A conservative garbage collector for C programs build on top of malloc/free package allocate using mallocuntil you run out of space is_ptr()determines if a word is a pointer by checking if it points to an allocated block of memory But, in C pointers can point to the middle of a block ptr Header So how to find the beginning of the block? Can use a balanced binary tree to keep track of all allocated blocks (key is start-of-block) Balanced-tree pointers can be stored in header (use two additional words) Head Data Size Left: smaller addresses Right: larger addresses Left Right
Exercise 3: Garbage Collection in C Mark and Sweep garbage collectors are called conservative if: a) They coalesce freed memory blocks during the sweep phase b) They treat everything that looks like a valid pointer as a pointer c) They perform garbage collection only when they run out of memory d) They do not free memory blocks forming a cyclic list
Exercise 4: Feedback 1. Rate how well you think this recorded lecture worked 1. Better than an in-person class 2. About as well as an in-person class 3. Less well than an in-person class, but you still learned something 4. Total waste of time, you didn't learn anything 2. How much time did you spend on this video (including exercises)? 3. Do you have any particular questions you d like me to address in this week s problem session? 4. Do you have any other comments or feedback?
