CSc 520 - Principles of Programming Languages
11 : Memory Management -- GC -- Uncooperative Languages
Christian Collberg
Department of Computer Science
University of Arizona
There is
some information which is necessary in order to perform
automatic memory management:
- We need to find the roots of the
object graph, i.e. the pointers
from the stack, registers, or global variables
which point to objects on the heap.
- We need to know the size, the beginning,
and end of each object.
- For each object we need to find
which of its fields are pointers.
- Unfortunately, some languages have been designed
so that it is impossible to determine this information.
- C and C++ are the two most popular such languages.
- C and C++ don't separate safe and unsafe features (such as
address and bit manipulation) which
are sometimes needed in systems programming.
- Modula-3 has similar unsafe features as C and C++
but they can be encapsulated into unsafe modules,
which don't mess up the safety of the main
(safe) part of the program.
- Most GC algorithms assume that there is always a pointer
to the beginning of every object. Depending on the
code generator, that may or may not be true.
1#1
There may be no pointer to s[0].
We need to know
- the roots of the object graph.
- the size, the beginning,
and end of each object.
- which object fields are pointers.
Finding Roots:
2#2
Finding the beginning:
3#3
Finding pointers:
4#4
Conservative Garbage Collection
- Works OK for uncooperative languages (C, C++)
where we can't distinguish between pointers and integers.
Sometimes fails to reclaim all garbage.
Main Ideas:
- Allocate memory in chunks. Each chunk
holds a collection of objects of a certain
size (i.e. it's easy to find the start of objects).
- Chunks are numbered. A pointer consists of 12 bits
of chunk number (5#5) + 20 bits of offset within
the chunk (6#6).
- To check whether a value 7#7 is a pointer to some
object we check that
-
8#8,
-
9#9
- the offset 6#6 is a multiple of the
object size in chunk 5#5.
Conservative1
Christian Collberg
2008-04-29