[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
OOC Garbage Collector Proposal
This is a proposal for an Oberon-2 based garbage collector for OOC.
Comments and discussion which will lead to an actual implementation
are invited.
Rationale
---------
1) Boehm's garbage collector has been designed to be a general-purpose
collector and consequently is much slower than an Oberon-2 specific
garbage collector could be which can take advantage of the compiler's
knowledge of the defined types and locations of pointers within
records and in static module areas.
2) The current compiler uses C-based memory management which, it has
been shown (see OFront paper by Dr. Josef Templ) that an Oberon-2
based storage allocator, can be up to 10 times faster than the use of
malloc. Add to this the overhead imposed by Boehm's redefinition of
this function and there could be real savings realized in a pure
Oberon-2 memory allocation scheme which is closely tied to the garbage
collector.
3) The current OOC runtime has no way of tracking resources which are
freed by Boehm's garbage collector. What is proposed here is
essentially a system which finalizes objects when they are freed by
the garbage collector. Many of the existing OOC projects can be
simplified if there were an object-based finalization scheme which was
tied into a garbage collector. Such a feature is particularly useful
with persistant objects and file descriptors.
Introduction
------------
Oberon-2 was the first modern language to actually require that
garbage collection be part of the runtime. This was facilitated by
the fact that Oberon-2 is a strongly typed language so the compiler is
able to provide information about where pointers are located in
records and the static module areas. As well, each object is tagged
with a type-descriptor so a garbage collector can easily determine
where pointers are located. Of course, since Oberon-2's introduction
other languages such as Java also provide garbage collection.
Generally, there is agreement that garbage collection is a "good
thing" because it results in more reliable software which is free from
dangling pointers caused by having memory freed while it is still in
use and memory leaks, caused by allocated memory which is never freed,
are virtually eliminated. What is still debated is whether a garbage
collector is as fast as manual memory freeing. I believe that the
answer to this question has been proven by all the existing Oberon
systems which are successfully performing in real world applications
such CAD, graphics and text editors, and networking software. With
the introduction of some new heuristics which determine the best time
to actually perform garbage collection, there should be no reason to
ever again have to manually free memory.
The following discussion is based on the ETH Report #156, "Oberon
Technical Notes", the second note entitled "An Integrated Heap
Allocator/Garbage Collector" and the fifth note entitled "Garbage
collection on Open Arrays."
The OOC-based garbage collector and heap allocator should be written
in Oberon-2 to ensure that the algorithms are both readable and
portable to other Oberon-2 systems. I propose to baseline the garbage
collector on an existing collector which is being used on the Oberon
systems running on PPC-based OSes. This collector includes memory
allocation features and object finalization as discussed above and is
written in Oberon-2.
Heap Allocator
--------------
Basically the allocator works by allocating a large block of memory
via a C-based routine (malloc). This block is then split up into
power-of-2-sized blocks depending on the caller's memory requirements.
The split blocks are then managed by the garbage collector. There are
a total of nine free lists maintained of which one is devoted to large
memory blocks and the remaining eight keep track of smaller blocks (in
multiples of 16 bytes) which are usually freed and allocated more
frequently.
Garbage Collector
-----------------
Garbage collection consists of a mark and sweep phase. During the
mark phase, all memory blocks which are pointed to by pointers located
on the stack or in other active memory blocks are "marked" in some
fashion. Usually this means setting a lower bit of the type tag
(i.e., lower four bits are unused if blocks are forced to be aligned
on 16-byte boundaries). The sweep phase then scans all the memory
blocks in the heap and places all the unmarked blocks back in the
appropriate free list. The mark & sweep phases need to be
uninterrupted so that memory references and the stack contents remain
consistent.
Finalization
------------
It is proposed that each allocated object have attached a dynamically
assigned procedure which is called by the garbage collector to
finalize any data block which is freed. The default will be to
initialize this object field with a NIL to indicate that no
finalization will be performed. It will be up the user to specify a
finalization procedure which can be installed for a specific object
during runtime.
OOC Support Required
--------------------
In order to guarantee an optimized garbage collection cycle it is
helpful to provide some hints to the garbage collector. For example,
in the record's type descriptor, it will be necessary to add the
offsets of the pointers contained within that record. Typically this
list of offsets can consist of a variable-length table which is
terminated by a negatively-valued sentinel. The type-descriptor block
size will obviously depend on this table size.
Secondly, it will be useful to store within a module's descriptor
block where the module's static data begins and its size. This start
address will have to be generated at runtime but the size should be
computable at compile-time. The garbage collector can then traverse
the module list and thus be able to look for any valid addresses which
point to an allocated memory block.
Thirdly, we will need a new kind of memory block called an ArrayBlk
which is distinct from a SysBlock (non-collected memory block) and a
RecordBlk (collected record block). This ArrayBlk will require some
additional fields. These fields comprise a type tag which points to
array element type descriptor, a data pointer which points to the
first accessible array element (thus one extra level of indirection is
needed to get at the array elements), a size of all the array
elements, and a pointer location which is reserved for the garbage
collector.
The ArrayBlk raises the issue of C-compatibility since OOC currently
passes arrays to C routines. While the above field locations make
life simpler for the garbage collector it might be possible to
relocate the fields in front of the type tag so the data is contiguous
from the array start address. When passed to a C routine, the extra
data fields would then be ignored.
Finally, several SYSTEM module additions will be needed to support the
finalization of types and user invocation of the garbage collector.
As well, objects will require an extra invisible field to support the
finalization procedure initialization. The following additions are
proposed:
PROCEDURE GC (markStack: BOOLEAN); (* to explicitly invoke GC *)
The markStack parameter specifies (if TRUE) that the run-time stack
should be scanned for pointer references. As an optimization,
markStack can be set to FALSE if it can be guaranteed that no objects
are anchored on the stack.
As well, the following are needed to support finalization:
TYPE
Finalizer = PROCEDURE (obj: SYSTEM.ADDRESS);
PROCEDURE RegisterFin (obj: SYSTEM.ADDRESS; finalize: Finalizer);
PROCEDURE FinalizeAll ();
The FinalizeAll procedure would be implicitly called at the end of
a main program.
When To Collect Garbage
-----------------------
One problem with existing garbage collectors (including those used on
the current Oberon systems) is that they tend to collect garbage at
the worst possible times. For example, most collectors are triggered
automatically when the NEW routine cannot find any memory blocks in
the free lists. This collection typically will be occurring in the
middle of some list creation or during execution of an algorithm which
uses dynamic data elements. These are precisely the times when we do
not want the collector to be active and slowing down these sorts of
activities. Ideally, we would want the collector to be activated when
we are waiting for user input or while the program is waiting for a
file to be opened. Unfortunately, the only way to do this is to
hardcode the GC collection at these places. Alternatively, it may be
possible to allow the user to specify when the GC should be activated
simply by embedding a GC call (from the SYSTEM) whenever the computer
is expected to be idling.
I would appreciate some discussion on this point.
Other Optimizations
-------------------
A second optimization is already implicit (somewhat) in the structure
of the memory free list implementation. Smaller blocks are easily
accessed and allocated. Since the most frequent allocations are of
smaller blocks, this design leads to an optimized allocator. This
architecture also helps to reduce the amount of memory fragmentation
since we use a "best-fit" algorithm to satisfy memory requests instead
of just blindly breaking up larger blocks.
-- Michael Griebling <grieblm@trt.allied.com>