2.

Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
1

Motivation
Manual memory deallocation is error-prone (e.g. in C/C++)
1. deallocation too early
p
q

dealloc(p);

"dangling pointer"
q.f = ...;

destroys some other object

2. deallocation missing
p

"memory leak"
object becomes unreachable
but wastes space

p = ...;

Garbage collection
A block is automatically reclaimed as soon as it is not referenced any more.
p

p
p = q;

not referenced any more

=> reclaimed
+ safe (avoids too early or missing deallocation)
+ convenient (code becomes shorter and more readable)
- slower (run-time system must do bookkeeping about blocks)

first time 1960: Lisp

today in almost all lang.:
Java, C#,
Smalltalk, Eiffel,
Scheme, ...

References (pointers)
When are new references created?
object creation:

p = new Person();

p
assignment:

q = p;

parameter passing:

foo(p);
void foo(Object r) {...}

q
r

When are references removed?

assignment:

p = s;

death of local pointers

at the end of a method:

void foo(Object p) {
...
}

reclamation of an object
that contains pointers:

p = null;

Garbage collection & object-orientation

Why is GC especially important in object-oriented languages?
Due to information hiding one never knows by how many pointers an object is referenced.

Example
A a = new A();
B b = new B(a);

How many pointers reference the A object?

a
b

class B {
private A p;
public B(A a) { p = a; }
...

The B object has a private pointer to the A object.

Clients of B don't know that because p is private.

Languages with GC
Java, C#, Eiffel, Smalltalk,
Lisp, Scheme, Scala, Oberon, ...

Languages without GC
C, C++, Pascal, Fortran,
Cobol, ...
4

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
5

Reference Counting
Oldest garbage collection technique (1960: Lisp)

Idea
Every object has a counter holding the number of pointers that reference this object
count
data
3
count ... hidden counter field

As soon as the counter becomes 0 the object is deallocated

Counter management
Compiler generates code for updating the counters
if (q != null) q.count++;

assignments

p = q;

IncRef(q);
DecRef(p);

parameters & local variables void foo(Object p) {

if (p != null) {
p.count--;
if (p.count == 0) dealloc(p);
}

IncRef(p);

...
DecRef(p);

deallocation of objects

void dealloc(Object p) {
for (all pointers q in *p) DecRef(q);
...
}

p = null;

a.count--;
b.count--;
c.count--;

Strengths
+ Unreferenced blocks are immediately reclaimed
(no delay like in other GC algorithms)
+ GC does not cause major pauses
(GC overhead is evenly distributed over the whole program)
+ GC can be done incrementally
DecRef(p)

background thread

if (p != null) {
p.count--;
if (p.count == 0) worklist.add(p);
}

while (!worklist.empty()) {
p = worklist.remove();
dealloc(p);
}

Weaknesses
- Pointer assignments and parameter passing impose some overhead
(GC costs are proportional to the number of assigments, even if there is no garbage)
- Counters need space in every object (4 bytes)
- Does not work for cyclic data structures!
p

p = null;

a.count--;
b.count--;

these counters never become 0

objects are never deallocated

Possibilities for dealing with cyclic data structures

ignore them (if there is sufficient memory)
require the programmer to break the cycle (b.next = null;)
try to detect the cycles (expensive)

Cycle detection (Lins92)

decRef(p)
p.count--;
if (p.count == 0)
dealloc(p);
else
mark p for lazy garbage collection;

Every node has one of the following colors:

black
white
grey
red

still referenced => keep it

unreferenced => deallocate it
under inspection by the GC
marked to be inspected by the GC

void decRef(Obj p) {
p.count--;
if (p.count == 0) {
p.color = white;
for (all sons q) decRef(q);
dealloc(p);
} else if (p.color != red) {
p.color = red;
gcList.add(p);
}
}

void incRef(Obj p) {
p.count++;
p.color = black;
}

From time to time do a garbage

collection on the mark list
void gc() {
do
p = gcList.remove()
until (p == null || p.color == red);
if (p != null) {
mark(p);
sweep(p);
collectWhite(p);
}
}
10

Cycle detection (continued)

p

Make all referenced objects grey

before mark(p)
void mark(Obj p) {
if (p.color != grey) {
p.color = grey;
for (all sons q) { q.count--; mark(q); }
}
}

p
after mark(p)
0

Make all unreferenced objects white

void sweep(Obj p) {
if (p.color == grey) {
if (p.count == 0) {
p.color = white;
for (all sons q) sweep(q);
} else restore(p);
}
}
void restore(Obj p) {
p.color = black;
for (all sons q) {
q.count++;
if (q.color != black) restore(q);
}
}

p
after sweep(p)
0

deallocate white objects

void collectWhite(Obj p) {
if (p.color == white) {
to break cycles
p.color = grey;
in collectWhite
for (all sons q) collectWhite(q);
dealloc(p);
}
}
11

Where is reference counting used?

In some interpreted languages where run time efficiency is not an issue
Lisp, PHP, ...

For managing references to distributed objects (COM, CORBA, ...)

e.g. COM
obj->AddRef();
obj->Release();

is called automatically by COM if a reference to an object (interface)

is created
must be called by the programmer if a reference is not needed any more

For managing references (links) to files (Unix, ...)

A file must not be deleted if it is still referenced by a link

12

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
13

Idea

roots
"live" pointer variables, which are not on the heap
(e.g. local variables)
heap

2 phases start when the heap is exhausted

1. Mark: Mark all objects that can be reached from roots (directly or indirectly)

2. Sweep: Traverse the heap sequentially and reclaim unmarked objects

14

Pros and Contras

Advantages
+ No overhead in assignments and method calls.
Compiler does not have to generate code for managing reference counters.
+ Needs only 1 mark bit per object (instead of a 4 byte counter field)
+ Cyclic data structures are handled correctly

Disadvantages
-

Noticeable pause while the GC runs (problematic for real-time systems)

Unfavorable for large heaps:

- Sweep time is proportional to the heap size.
- Mark time is proportional to the number of live objects

No compaction (heap remains fragmented)

Related objects are often spread over the whole heap (poor cache behavior).

15

Naive implementation
Simplistic assumption
all objects have the same type

class Block {
boolean marked;
Block left, right;
... // data
}

Mark algorithm
1

recursive depth-first traversal

void mark (Block p) {
if (p != null && !p.marked) {
p.marked = true;
mark(p.left);
mark(p.right);
}
}

5
4

Is this algorithm practical?

No!
Deep recursion might lead to stack overflow
16

Deutsch-Schorr-Waite algorithm
Schorr, Waite: An efficient machine-independent procedure for garbage collection
in various list structures, Communications of the ACM, Aug. 1967

Idea
Pointers are followed iteratively not recursively
The backward path is stored in the pointers themselves!

Example

State while visiting node 5

prev

cur

cur: currently visited node

prev: predecessor of cur;
node in which the backward
chain starts

No connection between cur and prev!

One has to remember, whether the backward chain
starts in left or in right

17

Objects with arbitrary number of pointers

Simplified assumption
all pointers are stored in an array
class Block {
int n;
int i;
Block[] son;
...
}

n
i
son

// number of pointers
// index of currently visited pointer
// pointer array
// data

i == -1
block is still unvisited;
used for marking

4
2

0
1
2
3

already visited
currently under visit
unvisited
data

18

Steps of the DSW algorithm

prev

prev
advance

cur

retreat
prev

cur

when
cur.i == cur.n

cur

p = cur.son[cur.i];
cur.son[cur.i] = prev;
prev = cur;
cur = p;

pointer rotation
p
cur.son[cur.i]

cur
prev

p = cur;
cur = prev;
prev = cur.son[cur.i];
cur.son[cur.i] = p;

pointer rotation
p
cur.son[cur.i]

cur
prev

19

DSW algorithm
void mark (Block cur) {
// assert cur != null && cur.i < 0
Block prev = null;
for (;;) {
cur.i++; // mark
if (cur.i < cur.n) { // advance
Block p = cur.son[cur.i];
if (p != null && p.i < 0) {
cur.son[cur.i] = prev;
prev = cur;
cur = p;
}

mark(p) is called for every root pointer p

Needs only memory for 3 local variables (cur, prev, p)

No recursion
Can traverse arbitrarily complex graphs

} else { // retreat
if (prev == null) return;
Block p = cur;
cur = prev;
prev = cur.son[cur.i];
cur.son[cur.i] = p;
}
}
}
20

Example
prev
cur

advance

prev

advance

retreat
prev

cur

prev
cur

cur

advance

retreat

prev

prev

retreat

prev
cur

advance

prev

cur

cur

cur

retreat

prev
cur

retreat
ready!

21

Type descriptors
Allow pointers to be at arbitrary locations in an object
class Block {
Block x;
Block y;
int data;
Block z;
}
Block a = new Block();
Block b = new Block();

0
4
8
12

tag
x
y
data
z
tag
x
y
data
z

type descriptor
of Block
20

objsize (=20)
0
4
12
sentinel

pointer
offsets

other
information

Every object has a hidden pointer (tag)

to its type descriptor

type descriptors are generated by the compiler for all classes; they are written to the object file
the loader allocates the type descriptors on the heap
new Block() allocates an object and installs in it a pointer to the corresponding type descriptor

22

Type tags
Format of a type tag
31

0
pointer to type descriptor

mark bit (1 = marked)

free bit (1 = free)
Type descriptors are 4 byte aligned (least significant 2 bits are 0)
When GC is not running, the mark and free bits are guaranteed to be 0
When GC is running, the mark and free bits have to be masked out

Pseudo type descriptors for free blocks

are directly stored in the free block
free
list

tag
objsize
next

objsize

In this way the block size of free and used

objects can be uniformly accessed via
tag.objsize.

23

Using the pointer offsets in mark()

Block

type descriptor

size
off
...
...
-16

cur
padr

off

Tag is "abused" for pointing to the offset of the

current son during mark()

16

void mark (Pointer cur) { // assert: cur != null && !cur.marked

prev = null; setMark(cur);
for (;;) {
cur.tag += 4;
off = memory[cur.tag];
if (off >= 0) { // advance
padr = cur + off; p = memory[padr];
if (p != null && !p.marked) {
memory[padr] = prev; prev = cur; cur = p;
setMark(cur);
}
} else { // off < 0: retreat
cur.tag += off; // restore tag
if (prev == null) return;
p = cur; cur = prev; off = memory[cur.tag]; padr = cur + off;
prev = memory[padr]; memory[padr] = p;
}
}
}

This is the GC of Oberon

4 bytes overhead per object
any number of pointers per object
pointers may be at arbitrary
positions
fixed memory requirements

24

Sweep phase
Heap after the mark phase
free list

allocated and marked

allocated but unmarked
free

Tasks of the sweep phase

traverses all heap blocks sequentially

merges adjacent free blocks
builds a new free list
clears the mark bits

Heap after the sweep phase

free list

25

Sweep algorithm

void sweep() {
Pointer p = heapStart + 4;
Pointer free = null;
while (p < heapEnd) {
if (p.marked) p.marked = false;
else { // free: collect p
int size = p.tag.size;
Pointer q = p + size;
while (q < heapEnd && !q.marked) {
size += q.tag.size; // merge
q = q + q.tag.size;
}
p.tag = p; p.tag.size = size;
p.tag.next = free; free = p;
}
p += p.tag.size;
}
}

allocated block
p

tag

size
size

free block
p

tag
size
next

When p.tag is accessed the free bit must

be masked to be 0 in free blocks

26

Lazy sweep
Problems
Sweep must visit every block (takes some time if the heap is hundreds of megabytes large)
In virtual memory systems any swapped pages must be swapped in and later swapped out again

Lazy sweep Sweep is done incrementally on demand

after mark()

scan
p = alloc(size);

free

marked
unmarked
free

no block in free list partial sweep

free

scan

until a sufficiently large block is freed and alloc() can proceed

free

scan
27

Lazy sweep (continued)

free
p = alloc(size);

scan

no sufficiently large block in free list partial sweep

free

scan

free

scan

alloc() can proceed

Requirements
Mark bits remain set while the program (the mutator) runs
(they must be masked out when the type tag is accessed)
mark() must only be restarted after the whole sweep has ended
28

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
29

Stop & Copy

The heap is divided into two parts: fromSpace and toSpace
New objects are allocated in fromSpace

top

toSpace

fromSpace
Simple sequential alloc(size)
top = top + size;

If fromSpace is full all live objects are copied to toSpace (scavenging)

root pointers
a

g
top

fromSpace

toSpace
30

Scavenging (phase 1)
a

1. Copy all objects that are directly referenced by roots

b
scan

fromSpace

d
top

toSpace

Change root pointers to point to the copied objects

Mark copied objects in fromSpace so that they are not copied again
Install a forwarding pointer to the copy in toSpace
Set a scan pointer to the start of toSpace
Set a top pointer to the end of toSpace

31

Scavenging (phase 2)
2. Move the scan pointer through the objects in toSpace
a

scan

top

if scan hits a pointer:

- copy the referenced object to toSpace (if not already copied)
mark the copied object in fromSpace and install a forwarding pointer to the copy
- change the pointer to point to the copy
a

d
top

scan

f
top

scan
a

ready if
scan == top

f
top
scan

32

Scavenging (phase 3)
3. Swap fromSpace and toSpace
b

f
top

toSpace

fromSpace

New objects are allocated sequentially in fromSpace again

Advantages

Disadvantages

single-pass algorithm
no mark()
purely sequential; no graph traversal
heap is compacted
(no fragmentation, better locality)
simple alloc()
run time independent of heap size;
depends only on the number of live objects

only half of the heap can be used

for allocation
copying costs time
objects change their address
=> pointers have to be adjusted

33

Comparison of the 3 basic techniques

Run time performance
Reference Counting
Mark & Sweep

time number of pointer assignments + number of dead objects

time number of live objects + heap size

Stop & Copy

time number of live objects

Overheads

for pointer assignments

for copying
for alloc()
for heap traversal

RC
***

M&S

S&C
***

*
***

GC and virtual memory

Sweep swaps all pages in (others are swapped out)
S&C can use big semi-spaces, because toSpace is originally on the disk anyway.
While toSpace gets full its pages are swapped in and fromSpace gets swapped out

34

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
35

Mark & Compact

Compacting variant of Mark & Sweep
Mark all reachable blocks

Sweep 1: For every marked block compute its address after compaction
0

16

32

Sweep 2: Adjust roots and pointer fields to point to the new addresses
Sweep 3: Move blocks to the computed addresses

16

32

Advantages

Disadvantages

+
+
+
+

- objects must be copied (moved)

- needs an additional address field per block
- 3 sweeps necessary => slow

removes fragmentation
simple sequential alloc()
order of objects on the heap is retained
good locality (virtual memory, caches)

36

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
37

Generation scavenging -- idea

Variant of Stop&Copy

Problems 1) Long-living objects must be copied in every GC run.

2) Most objects die young!

Solution

Distinguish between short-living and long-living objects

newFrom

top1

Young generation
(short-living objects)
newTo
Old generation
(long-living objects)

top2

oldFrom

oldTo

New objects are always allocated in newFrom

GC for newFrom is performed more frequently than for oldFrom;
objects that have been copied n times get "tenured" (are copied to oldFrom)
Good for languages with many short-living objects (e.g. Smalltalk)
- only 5% of the objects survive the first collection
- only 1% of the objects survive the second collection (but those live very long)
newFrom often small (< 128 KB); managed with Stop&Copy
oldFrom often large; managed with Mark&Compact or with an incremental GC

38

Cross-generation pointers
Pointers from newFrom to oldFrom
newFrom

newTo

oldFrom

oldTo

Before every old-GC a new-GC is performed

Pointer from new to old are detected and
considered as roots for old-GC

Pointers from oldFrom to newFrom

newFrom

newTo

oldFrom

oldTo

remembered set

If an object is copied from newFrom to oldFrom,

any pointers from old to new are stored in a
so-called "remembered set"
The remembered set is used as a root table
for new-GC
There is empirical evidence that there are more
pointers from newFrom to oldFrom than vice versa

39

Write barriers
Problem: pointer assignments
new

new
newFrom

old

newFrom

old.f = new;

oldFrom

old

oldFrom

Installs a pointer from oldFrom to newFrom.

How does the GC notice that?

Compiler must generate "write barriers"

At every pointer assignment
old.f = new;

the following code must be generated:

if (old in oldFrom && new in newFrom)
add Addr(old.f) to rememberedSet;

Check can be implemented efficiently

(see later)
Such pointer assignments are rare
Costs about 1% of run time in Java
Optimizations possible, e.g.:
assignments to this.f in a constructor cannot
install a pointer from oldFrom to newFrom
40

Tenured garbage
Dead objects in the old generation
newFrom

oldFrom

Tenured garbage may keep dead objects in the young generation alive
=> should be avoided if possible

Tenuring threshold
n: Number of copy runs until an object is copied to oldFrom
Dilemma
n small => much tenured garbage
n large => long-living objects remain in young generation longer than necessary
=> long GC times
41

Adaptive tenuring (Ungar 1988)

Keep tenuring threshold flexible (depending on the amount of live objects in newFrom)
Object age
Every object remembers how often it was copied in the young generation (age field)

Age table
How many bytes of every age are in newFrom?
age

bytes

1
2
3

50000
9000
8000

i.e. 8000 bytes were already copied 3 times

Watermark
Assume that the tolerated maximum GC pause is 1 ms
=> watermark = max. number of bytes, which can be copied in this time

42

Adaptive Tenuring (continued)

Situation after copying
survived objects < watermark
toSpace

=> tenureAge =

watermark

i.e. during the next GC run no objects are

copied to oldSpace

survived objects > watermark

=> tenureAge must be chosen such that at least d bytes are tenured
in the next GC run
1
2
3

50000
9000
8000

e.g. d = 10000 => all objects with age >= 2 are

copied to oldFrom in the next GC run.

43

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
44

Motivation
Goal
Avoid long GC pauses (pauses should be less than 1 ms)

Application areas
For soft real-time systems (hard real-time systems should not use a GC at all)
For the old generation in a generational GC
GC pause is longer for the old generation because:
- old generation is larger than young generation
- there are more live objects in the old generation than in the young generation

Idea
GC (collector) and application program (mutator) run in parallel (interleaved)
a) collector runs continuously as a background thread
b) collector stops the mutator, but does only a partial collection

Problem
Mutator interferes with the collector!
Can change data structures, while the collector is visiting them
45

Suitability of basic techniques for incr. GC

Reference Counting

yes

Counter updates do not cause substantial pauses

if counter == 0
- object reference is written to a worklist
- worklist is processed as a background thread
(reclaiming objects and writing new references to the worklist)

Mark & Sweep

no

Mutator may interfere with the mark phase

Sweep phase can run in the background,
if the mutator ignores the mark bits

Stop & Copy

a
b

a.f = d;
c

no

b is kept alive
d is collected!

Mutator may interfere

M&S and S&C must be modified in order to be able to run incrementally

46

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
47

Tricolor marking
Abstraction of an incremental GC, from which various concrete algorithms can be derived

Idea: all objects have one of the following colors

white
black
grey

yet unseen objects (potentially garbage)

reachable and already processed objects
objects that have been seen but not yet processed
(pointers to them must still be followed)

For example in Stop&Copy

fromSpace

toSpace

scan

top

Invariant
There must never be a pointer from a black object to a white object
48

What problem can arise?

Example
a

Collector starts running

a

Problem source

Mutator interferes

A pointer to a white object is installed

into a black object

a.next = c;
b.next = null;

Collector continues
a

c is erroneously considered as garbage

b is erroneously kept alive
49

Problem solution
We have to avoid that a black object points to a white object
a

a.next = c;
b.next = null;

This can be avoided in 2 ways

Read barrier
The mutator must not see white objects.
Whenever it reads a white object, this object
is "greyed" (i.e. marked for processing)
a.next = c;

Write barrier
If a white object is installed into a black object
the black object is "greyed"
(i.e. it must be revisited)
a.next = c;

Read barriers are more conservative,

because the white object that is read
need not be installed in a black object
Read barriers are expensive if implemented in software.
There are more pointer reads than
pointer writes
Read barriers usually for Stop&Copy
Write barrier usually for Mark&Sweep

In both cases b is left over as "floating

garbage"; but it is reclaimed in the
next GC run.
50

Baker's algorithm (read barrier)

a

1. Copy all objects that are directly referenced by roots

a

d'

scan top

2. New objects are allocated at the end of toSpace

they are conceptually black (they do not contain pointers to white objects)
a

d'

scan top

new

3. At every alloc() do also an incremental scan/copy step

a

b'

d'

scan top

new

51

Baker's algorithm (continued)

a

b'

d'

scan top

new

4. If the mutator accesses a white object, this object is copied and becomes grey
(read barrier)
e.g. after accessing a
a'

b'

d'

scan

top new

Read barrier: a = get(a);

Mutator sees only toSpace objects

Pointer get (Pointer p) {

if (p points to fromSpace) {
if (p not already copied)
copy p to top;
p.forward = top;
top = top + p.size;
}
p = p.forward;
}
return p;
}

Can also be implemented with virtual memory:

fromSpace is protected so that every read access causes a trap

Problems
- Requires a read barrier for every read access to a white object (20% of the run time)
- Can only be implemented efficiently with special hardware or OS support (virtual memory)
52

Write barrier algorithms

Catch pointer writes, not pointer reads
+ Writes are less frequent than reads (5% vs. 15% of all instructions) => more efficient
- Works only for Mark&Sweep, not for Stop&Copy:
Stop&Copy requires read barriers, because if an object that has already been copied
is accessed again in fromSpace the access must be redirected to the copy in toSpace

Problematic case
p

p.f = q;
q = ...;

Two conditions must hold in order to cause a problem:

a) a white object is installed in a black object (p.f = q;)
b) all other pointers to the white object disappear (q = ...;)
At least one of these conditions must be prevented

2 kinds of write barrier algorithms

Snapshot at beginning (prevents condition b)
Incremental update (prevents condition a)
53

Snapshot at beginning
Objects stay alive, if they were reachable at the beginning of the GC run
p

p.f = q;

obj

q
obj was reachable and thus
must stay alive
obj

If a pointer is removed from an object

the object is greyed

Prevents that the last pointer to an object disappears (condition b)

p
q
p
q
a) p.f = q;
b) q = ...;

Implementation:
ptr = ...;

worklist.add(ptr);
ptr = ...;

Write barrier generated by the compiler;

worklist is processed by the GC later

Catches all pointer assignments (not only assignments to pointers in black objects)
Very conservative!

54

Incremental update
Objects stay alive, if they are reachable at the end of the GC run
p

a) p.f = q;

q
obj

obj

if q disappears,
obj is visited nevertheless
if a pointer to a white object is
installed in a black object
the white object is greyed

Prevents that white objects are installed in black ones (condition a)

Implementation:
Write barrier generated by the compiler;
p.f = q;
if (black(p) && white(q))
worklist is processed by the GC later
worklist.add(q);
p.f = q;

Catches only assignments to pointers in black objects

(more accurate than "snapshot at beginning")

55

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
56

Idea
Incremental Stop&Copy algorithm with write barriers (primarily for old generation)

The heap is divided into segments ("cars") of fixed size (e.g. 64 KBytes)
"car"

"car"

"car"
"train"
Every car has a remembered set:
addresses of pointers from later cars
to this car (= additional roots)

Every GC step collects exactly 1 car (the first one)

- copies live objects to other cars
- releases the first car
GC of a single car is fast => no noticeable overhead

Objects that are larger than 1 car are managed in a separate heap
(large object area)
57

Dealing with dead cycles

Problem
Dead cycle across several cars
x

If the first car is collected we don't see

that x is dead, because it is referenced from
a later car.

Simple solution
All objects of a dead cycle must be copied into the same car

...

If this car is collected the whole cycle is

released together with the car

Does not always work ...

... because the objects of a cycle
may not fit into a single car
=> This is where the train algorithm comes in
58

Train algorithm
Cars are grouped into several trains
1.1

1.2

1.3

train 1
2.1

2.2

train 2
3.1

3.2

3.3

3.4

train 3
Order of processing: 1.1 < 1.2 < 1.3 < 2.1 < ... < 3.3 < 3.4

Our goal is to accumulate dead cycles in the first train

train 1

Objects that are referenced by roots or from

other trains are evacuated to later trains

train 2
If no object in the first train is referenced from outside the first train
=> release the whole first train!

59

Remembered sets
Remembered set of a car x
Contains addresses of pointers from later cars to x
a

c
b

c d

Additionally, there is a list of roots pointing from outside the heap

into the cars

60

Updating remembered sets

Write barriers

p
f

p.f = q;
p.f
Remembered Set

If car(q) is before car(p) (i.e. if this is a pointer from back to front)

=> add address of p.f to remembered set of car(q)

61

Car ordering
Cars are logically ordered!
Their physical addresses need not be in ascending order (cars may be anywhere in the heap)
train 1 1.1

1.2

40000 10000

train 2 2.1

1.3
20000

physical addresses
(hexadecimal)

2.2

50000 00000

train 3 3.1

3.2

70000 90000

3.3

3.4

30000

80000

Car table
maps physical address to car number
e.g. car size 2k (e.g. 216 bytes = 64 KBytes)
car index n = (adr - heapStart) >> k;
tab[n] tells us which car is stored at adr

n
0 0000
1 0000
2 0000
3 0000
4 0000
5 0000
6 0000
7 0000
8 0000
9 0000
10 0000

tab
2.2
1.2
1.3
3.3
1.1
2.1
3.1
3.4
3.2
...

Example
pointer from 30AF4 to 50082
from tab[3] to tab[5]
from 3.3 to 2.1
from back to front

62

Incremental GCstep
r

a (from the same train)

b (from some other train)

a b

if (there are no pointers to the first train from outside this train)
release the whole first train;
else {
car = first car of first train;
copy
for (all p in rememberedSet(car)) {
copy pobj to the last car of train(p);
if full, start a new car in train(p);
}
for (all roots p that point to car) {
copy pobj to the last car of the last train (not to the first train!);
if full, start a new train;
}
scan
for (all p in copied objects)
if (p points to car) {
copy pobj to last car of train(p);
if full, start a new car in train(p);
} else if (p points to a car m in front of car(p))
add p to rememberedSet(m);
release car;
}

Additional considerations
How to find pointers from outside
this train: inspect roots and
remembered sets of all cars
of this train.
If there are multiple pointers to
the same object => don't copy
this object twice, but install a
forwarding pointer.
Cars and trains must be linked
in order to find the first and the
last car of a train.

63

Example
B, F

root
R

Assumption: our cars have only

space for 3 objects

copy R to the last car of the last train (because it is referenced from a root)
copy A to the last car of train(B)
copy C to the last car of train(F)

B
root

A
64

Example (continued)
R, C

B
root

copy S to the last car of train(R); no space => start a new car in train(R)
copy D to the last car of train(C); no space => start a new car in train(C)
copy E to the last car of train(D)
T
F

B
root

A
S

65

Example (continued)
S, E

T
F

B
root

copy T to the last car of train(S)

copy F to the last car of train(E)
copy C to the last car of train(F); no space => start a new car
F
D

B
root

A
S

66

Example (continued)
C

F
D

B
root

A
S

no pointers to the first train from ouside this train => release the whole first train

67

Example (continued)
B
root

copy R to the last car of the last train;

Since there is only one train, start a new train
B

A
S

root

68

Example (continued)
B

A
S

root

no references into the first car => release first car

69

Example (continued)
R

root

copy S (and also T) to the last car of train(R)

T
root

ready!
Only live objects survived
In every step at least 1 car was released => progress is guaranteed
70

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
71

Root pointers
Roots are all live pointers outside the heap
local variables on the stack
reference parameters on the stack (can point to the middle of an object!)
global variables in C, C++, Pascal, ...
(static variables in Java are on the heap (in class objects))
registers
stack

registers

global variables

heap

All objects that are (directly or indirectly) referenced from roots are live
Mark & Sweep:
for (all roots p) mark(p);
sweep();

Stop & Copy:

for (all roots p) copy referenced object to toSpace;
scan();

72

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
73

Global pointers
Global pointer variables in Oberon
For every module the compiler writes a list of global pointer addresses to the object file
The loader creates a pointer offset table for every loaded module

module A

module B

module C

list of loaded modules

global pointer tables

for (all loaded modules m)

for (all pointers p in m.ptrTab)
if (p != null && *p not marked) mark(p);

Static pointer variables in Java

Fields of class objects (offsets stored in type descriptors)
Loader creates class objects and stores their addresses in the roots table

74

Local pointers
For every method the compiler generates a table with pointer offsets
void foo(Obj a, int b) {
int c;
Obj d;
...
}

fromPC toPC pointer offsets registers with pointers

// a ... Offset 0
// d ... Offset 3

foo()
bar()
baz()

1000

1250

Compiler writes these tables to the object file

Loader loads them into the VM

Stack traversal in order to find local pointers

for (all stack frames f) {
meth = method containing pc of f;
for (all p in meth.ptrTab) mark(p);
for (all r in meth.regTab) mark(r);
}

75

Blocks with different pointer offsets

Blocks of the same method can have different pointer offsets (in Java)
pc1

if (...) {
int a;
Obj b;
...
} else {
Obj c;
int d;
}

0
1

a
b

0
1

c
d

pc2
pc3

pc4

Pointer offset table must have several regions per method

from

to

pointer offsets

pc1

pc2

pc3

pc4

In the Hotspot VM this is solved via safepoints (see later)

Also allows that a register may contain a pointer or a non-pointer at different locations

76

Pointers in objects
class Person {
int id;
String name;
String address;
int zip;
}

Type descriptors contain pointer offsets

p

0
1
2
3

tag
id
name
address
zip

type descriptor
1
2

pointer offsets

Compiler writes type descriptor to the object file

Loader loads type descriptor when the corresponding class is loaded
new Person() installs the type descriptor in the Person object

77

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
78

Conservative garbage collection

Used if the compiler does not generate pointer tables (e.g. in C/C++)

"Guess" which memory locations contain pointers

Check every word w (on the stack, in the global data area, in heap objects, in registers)
w is a possible pointer if
- w points to the heap (easy to check)
- w points to the beginning of an object (difficult to check)

Guessing must be done conservatively

If the guess is wrong (w is actually an int and not a pointer), no harm must occur
What if the guess was wrong?
Mark&Sweep: an object is marked although it may be garbage
=> no harm
Stop&Copy: the "wrong pointer" (which is actually an int) is changed to the new object location
=> destroys data
Ref. Counting: only for searching pointers in deallocated objects;
Counter is decremented, although the object was not referenced by w
=> counters become inconsistent
79

Implementation with a candidate list

All possible pointers are collected in a list
for (all words w in stack, global data and registers) {
if (heapStart <= w < heapEnd) candidates.add(w);
}
candidates.sort();
i = 0; p = heapStart;
while (i < candidates.size() && p < heapEnd) {
if (candidates[i] == p) {
if (!p.marked) mark(p);
i++; p = p + p.size;
} else if (candidates[i] < p) {
i++;
} else { // candidates[i] > p
p = p + p.size;
}
}

candidates
i

heap

Requires a full heap traversal to find the pointers

In principle, mark() must inspect all words of an object in a similar way
Sometimes a mixture: pointer tables for objects, conservative GC for stack etc. (e.g. in Oberon)

80

Implementation with an allocation bitmap

Blocks are allocated in multiples of 32 bytes (32, 64, 96, ...)
There is a bitmap with 1 bit per 32 byte of heap area
An address a is the beginning of a block bit[a >> 5] == 1
heapStart

Heap
0

32

64

96

128

allocation bitmap
bit
b
= b - (heapStart >> 5)

Bitmap requires 1 bit per 32 bytes (256 bits) => 1/256 = 0.4% of the heap
alloc() must set the bits
sweep() must reset the bits
for (all words w in stack, global data and registers) {
if (heapStart <= w < heapEnd && bit[w >> 5] && !w.marked) mark(w);
}

+
+
-

does not need a candidate list

does not need an additional heap traversal
overhead for maintaining the bitmap
bit operations are expensive

81

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
82

GC in multi-threaded systems
Problems
Several mutator threads -- all must be stopped before GC runs
GC is not allowed at all locations, e.g.
MOV EAX, objAdr
ADD EAX, fieldOffset
MOV [EAX], value

GC is not allowed here, because the object

may be moved

Safepoints (GC points)

Locations where GC is allowed
Threads can only be stopped at safepoints
For every safepoint there is
- a table of pointer offsets in the current stack frame
- a list of registers containing pointers

Stopping threads at safepoints can be implemented in 2 ways

Safepoint polling
Safepoint patching
83

Safepoint polling
Mutator checks at safepoints if GC is pending

Safepoints

method entry (enter)

method exit (return)
system calls
backward jumps

guarantees that every thread reaches the next

safepoint quickly

Compiler emits the following code at every safepoint

if (gcPending) suspend();

or:

MOV dummyAdr, 0

If gcPending, the memory

page dummyAdr is made
readonly
=> Trap => suspend()

If the system runs out of memory ...

gcPending = true;
suspend all threads;
for (each thread t)
if (not at a safepoint) t.resume(); // let it run to the next safepoint
// all threads are at safepoints
collect();
gcPending = false;
resume all threads;

Thread1
...
PC ...
...
...
...
...

Thread2
...
...
...
...
Safe...
point
...
84

Safepoint patching
Safepoints are patched with instructions that cause a thread to be suspended

Safepoints
method call
method exit (return)
backward jump

because of dynamic binding the invoked method is unknown

=> would require too many methods to be patched

If the system runs out of memory ...

suspend all threads;
for (each thread t) {
patch next safepoint with a trap instruction;
t.resume(); // let it run until the next safepoint
}
// all threads are at safepoints
collect();
restore all patched instructions;
resume all threads;

PC at the time when the

system runs out of memory

call trap

call trap

85

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
86

Goal
Cleanup work to be done before an object is reclaimed
closing open files
terminating threads
e.g. in Java
class T {
...
protected void finalize() throws Throwable {
... // cleanup work
super.finalize();
}
}

is automatically called before a T object is reclaimed

avoid finalizers if possible
reclamation of finalized object is delayed (see later)

87

Finalization during GC (e.g. in Oberon)

Objects with a finalize() method are entered into a finalization list when they are allocated
=> new() takes a little longer
Finalization list entries must not be considered as pointers,
otherwise these objects would never be garbage collected

Finalization during Mark&Sweep

mark();
for all unmarked objects in the finalization list:
- obj.finalize();
- remove obj from finalization list
sweep();

Finalization during Stop&Copy

scan();
for all objects in the finalization list, which have not been copied
- obj.finalize();
- remove obj from finalization list
=> increases the GC pause!
88

Finalization in the background

(e.g. in Java and .NET)
mark();
for all unmarked objects obj in the finalization list
- worklist.add(obj);
- set mark bit of obj
sweep();
background thread processes worklist
- calls obj.finalize();
- clears mark bit
- remove obj from finalization list
object is collected during the next GC run

Finalization can happen at any time after GC!

No guarantee that finalization will happen at all
until the end of the program

=> no substantial increase of GC pauses

but objects that have to be finalized are released with a delay
Object resurrection
protected void finalize() throws Throwable {
...
globalVar = this;
}

brings finalized object to life again!

next GC will detect this object as live => keep it

if object finally dies => no finalizer call again!
89

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
90

Heap layout
Two generations
young generation

fromSpace

nursery

toSpace

Stop&Copy
New objects are allocated in the nursery
if full => copy fromSpace + nursery to toSpace
advantage: less waste for toSpace
if overflow => copy remaining objects to old
after n copy passes an object is copied to old
n is variable (adaptive tenuring)
many new objects => faster "tenuring"

old generation
Mark&Compact
is executed less frequently

Remembered set
List of all pointers from old to young
An entry is made
- if an object with pointers to other young objects is tenured
- if a pointer to young is installed in an old object (detected by a write barrier)
91

Write barriers
Card-marking scheme
heapStart

heap

divided into
"cards" of 512 bytes

dirty
= a - (heapStart >> 9)

dirty table: 1 byte(!) per card (byte ops are faster than bit ops)
1 ... card unmodified
0 ... card modified

If a pointer is installed into an object: obj.f = ...; (no matter where it points to):
LEA
MOV
SHR
MOV
ADD
MOV

EAX, obj
EBX, EAX
EBX, 9
byte ptr dirty[EBX], 0
EAX, offset(f)
[EAX], ...

3 instructions per pointer write

generated by the compiler (only for field assignments, not for assignments to pointer variables)
write barriers cost about 1% of the run time
GC searches all dirty cards in oldSpace for objects;
any pointers in them that point to newSpace are entered into rememberedSet
92

Searching for objects in cards

Objects may overlap card boundaries
d1

d2

heap consisting of cards

d1 d2

offset table
1 byte per card
how far does the first object extend into the predecessor card?
if it overlaps the whole predecessor card:
offset = 255 => search one card before
Objects are aligned to 4 byte boundaries
=> table holds offset / 4

for (all dirty cards i in oldSpace) {

obj = heapStart + 512 * i; cardEnd = obj + 512; j = i;
while (offset[j] == 255) { obj = obj - 512; j--; }
obj = obj - offset[j] * 4;
while (obj < cardEnd) {
for (all pointers p in obj.ptrTab)
if (p points to newSpace) rememberedSet.add(p);
obj += obj.size;
}
}

27

28

29

32

obj
27

27
1

cardEnd
28
8

29

28
0

29
1

offset
dirty
93

Object layout
class A {
Obj x;
int y;
Obj z;
}
class B extends A {
int a;
Obj b;
Obj c;
}

aging
4

mark, lock
26
tag
x
z
y
b
c
a

2
2
2

All pointers of a class are stored in a contiguous area

2 words overhead per object
First word is used for the new target address in Mark&Compact

94

Pointers on the stack

Stack can hold frames of compiled or interpreted methods

For interpreted methods

Analyze the bytecodes to find out where the pointers are

For compiled methods

Compiler generates a pointer table for every safepoint
(call, return, backward branch and every instruction that can throw an exception)
GC can only happen at safepoints
Safepoint polling: at every safepoint there is the instruction:
MOV dummyAdr, 0

If GC is pending, the memory page dummyAdr is made readonly => trap => suspend()

95

G1 -- Garbage-first collector
Alternative GC for server applications (large heaps, 4+ processors)
Since Java 6

Main ideas
1. Incremental GC (similar to train algo)
A

...

RSA

RSB

Heap is divided into equally sized regions (~1MB)

Remembered set per region (contain pointers from
any region to this region; in contrast to train algo)

RSC

2. Collect regions with largest amount of garbage first

...
100

250

270

Regions are logically sorted by collection costs

- number of live bytes to be copied
- size of remembered set

3. Allocate new objects in "current region" (if full, start new current region)
96

G1 -- Computing live objects

Global marking phase (started heuristically from time to time)
Mark all live objects (concurrently to the mutator)
foreach (root pointer r) mark(r);
while (!todo.empty()) {
p = todo.remove();
foreach (pointer q in *p) mark(q);
}

mark (p) {
if (*p not marked) {
mark *p;
todo.add(p);
}
}

Mark bits are kept in separate bitmap (1 bit per 8 bytes)

avoids synchronization between mutator and marker

97

G1 -- Building remembered sets

Write barriers
Mutator threads use write barriers to catch pointer updates during marking.
Snapshot at beginning: make object grey if pointer to it is removed
p

q
f

p.f = q;

has to be visited for marking

Write barriers also build (update) the remembered sets

q

p.f = q;

RS

98

young

G1 -- Generations
eden regions

those in which new objects have been allocated recently

survivor regions

contain objects with age < tenureAge

old regions

all other regions

Incremental evacuation step (while all mutator threads are stopped)

Evacuate young regions to survivor regions or old regions
eden

eden

survivor survivor

old

old

old

...

Adapt number of young regions such that evacuation does not exceed tolerated pause time
If time permits, evacuate also old regions with largest amount of garbage
young

survivor survivor

old

old

old

old

...

tolerated GC pause time

For evacuation of region R use rootsR and RSR

After evacuation update remembered sets
For details see: David Detlefs et al.: Garbage-First Garbage Collection.
In Proc. Intl. Symp. on Memory Management (ISMM'04), Vancouver, Oct 24-25, 2004

99

2. Garbage Collection
2.1 Motivation
2.2 Basic techniques
2.2.1 Reference Counting
2.2.2 Mark & Sweep
2.2.3 Stop & Copy

2.3

Variants
2.3.1 Mark & Compact
2.3.2 Generation scavenging

2.4

Incremental garbage collection

2.4.1 Tricolor marking
2.4.2 Train algorithm

2.5

Root pointers
2.5.1 Pointer tables
2.5.2 Conservative garbage collection

2.6 Garbage collection in multi-threaded systems

2.7 Finalization
2.8 Case study: Java Hotspot VM
2.9 Case study: .NET
100

GC in .NET
Mark & Compact with multiple generations
1. Objects are allocated sequentially (no free list)

top

2. If the heap is full => mark()

A

3. compact()
New objects are allocated sequentially again
A

generation 1

D
generation 0

top

4. If the heap is full => mark&compact only for generation 0!

faster; most dead objects are in generation 0

generation 2

generation 1

generation 0

top

101

GC in .NET
generation 2

generation 1

generation 0

top

Currently restricted to 3 generations

From time to time there is a GC of generations 0+1 or generations 0+1+2 (heuristic)
Pointers from generation 1+2 to generation 0 are detected with write barriers
- GetWriteWatch(..., oldGenArea, dirtyPages) returns all dirty pages in oldGenArea
- these must be searched for pointers to generation 0
Objects larger than 20 KBytes are kept in a special heap (Mark&Sweep without compaction)
GC of generation 0 takes less than 1 ms
Threads are stopped at safepoints before the GC runs

102