 |
| Class Diagram of Counters |
High Level Language Virtual Machines is a core topic of interest for the researchers who are into virtual execution environments. As an open source virtual machine released to 16 universities, as early as 2001, Jikes RVM has been a major drive for many researches. Garbage Collectors for the Jikes RVM are constructed by the framework known as the Memory Management Toolkit (MMTk). Key Compositional Elements in MMTk are utilities, policies, and plans. Apart from these, package org.mmtk.harness contains the MMTk harness test cases. Sanity checks are included in the package org.mmtk.harness.sanity. GcSanity is the collection sanity checker, that takes snapshots before and after a collection to ensure that the live objects after a collection are the same that exist before the collection. Further options are implemented in the classes of org.mmtk.harness.options. We have looked at policies and plans. In this post, we will look at the MMTk utility package, which implements the MMTk mechanisms.
MMTk comes with the
utility classes that provides mechanism for the memory management,
across multiple policies and plans that use those policies. An ideal
example showing the usage of the utility package is, the interface
Constants. All the
classes either implement the Constants interface, or are sub classes
of the classes that implement the interface.
1.
Allocation
The
package org.mmtk.utility.alloc
handles the allocation. Allocator is the base
class providing the basis for the processor-local allocation. This
provides the retry mechanism, to prevent the slow-path allocation
causing a garbage collection, violating the assumption of
uninterruptibility. Allocator also ensures that requests are aligned
according to requests. This class is very crucial in garbage
collection as the base class for all the allocator algorithms.
Improper handling of this will make it hard to trace the bugs, where
allocations may cause a garbage collection, or a garbage collection
may immediately follow an allocation.
The method alignAllocation() accepts a region to
be aligned, and aligns up the request, according to the requested
alignment and offset, optimizing with the known alignment for the
allocator algorithms. This method returns the aligned up address.
Consecutive allocation failure for the threads are
counted by determineCollectionAttempts(). fillAlignmentGap() gets
the start and end addresses, and fills the region with the alignment
value. The minimum size guaranteeing the allocation of a given number
of bytes at the specified alignment is calculated by
getMaximumAlignedSize().
All allocators should
use the final method, allocSlowInline() for
the slow path allocation. This
method attempts
the protected method allocSlowOnce() multiple
times, which is
defined in the subclasses. This method ensures safe execution by
taking care of the thread/mutator context affinity changes, whilst
allowing the collection to occur.
2.
Bump Pointer Allocation
This is implemented by
the BumpPointer class,
which extends the abstract class Allocator. Bump Pointer scans
through the allocated objects linearly. To achieve parallelism, this
class maintains a header at a region of 1 or more blocks granularity.
The minimum region size is 32678 bytes. Hence the 3 or 4 word
overhead is less than 0.05% of all space. BumpPointer is initialized
by providing the space to bump point into, indicating whether the
linear scanning is allowed in the region. The method linearScan()
performs a linear scan through
the objects allocated by the bump pointer, and scanRegion()
scans through a single
contiguous region.
Intra-block allocation requires only a load, addition
comparison and store, and hence is fast. The allocator will request
more memory, if a block boundary is encountered. The scanned objects
maintain affinity with the thread which allocated the objects in the
region. This class relies on the supporting virtual machine
implementing the getNextObject and related operations.
Space is allocated for a new object, by calling alloc().
This method is frequently executed, and is sensitive to the
optimizing compiler. Whenever the bump pointer reaches the internal
limit, allocSlow() is called.
This method should never be inlined by the optimizing compiler, and
hence is annotated with @NoInline, to
force out of line.
Bump pointer can be
re-associated to a different space by calling rebind(),
providing the new space to which
the pointer to be associated to. The bump pointer will be reset such
that it will use the new space for the next call to alloc().
Address is a
stub implementation of an Address type, used by the runtime system
and collector to denote the machine addresses. An allocation unit is
denoted as a card, which
is marked by an address that lies within the card. Providing the
address of the object creating a new card, the address that lies
within the card, and the size of the pending allocation in bytes,
createCardAnchor() creates
a record, where the start of the card is relative to the start of the
object. The start of the card corresponding to the given address can
be retrieved by calling getCard().
Similarly, the address of the card metadata can be retrieved by
providing an address from the card, calling getCardMetaData().
Next region from the
linked list of regions can be retrieved using getNextRegion().
Similarly,
setNextRegion() is used to set
the next region in the linked list. clearNextRegion()
clears the next region pointer
in the linked list.
The DATA_END address
from the region header can be retrieved using getDataEnd(),
by providing the bump pointer
region address. setDataEnd() is
used to set the new DATA_END address from the header. Similarly,
getRegionLimit() and
setRegionLimit()
return or store the end address of the given region, respectively.
The lowest address where the data can be stored can be retrieved by
getDataStart(), for the given region. updateMetaData() is
used to update the metadata, reflecting the addition of a new region.
Where a bump pointer region has been consumed, but the contiguous
region is available, consumeNextRegion() consumes
it and returns the start of the region satisfying the outstanding
allocation request.
3.
Block Allocation
Blocks are a unit of storage of 2 ^ n bytes, that are
non-shared (thread-local) and coarse-grained. Virtual memory resource
provides virtual memory space. Here, pages consumed by blocks are
accountable for the memory resource. BlockAllocator implements
various sizes of Block data structure. alloc() allocates
a block and returns the first usable bytes of the block. A block is
freed by calling free(). If
the block is completely free, the block is returned to the virtual
memory resource. Otherwise, if the block is just a sub-page block,
the block is added to the free list.
4. GCspy Integration
GCspy 2.0 is a
tool that helps to analyse the heap, that often is used to understand
the memory usage and effectiveness of garbage collectors in our
project. The development of GCspy however lags behind that of the
Jikes RVM core [10]. The data for GCspy is gathered using
gcspyGatherData() in the
classes. The package
org.mmtk.utility.gcspy contains
the classes for the GCspy integration, and
org.mmtk.utility.gcspy.drivers contains
the GCspy drivers for the MMTk collectors.
5.
Treadmill
Each
instance of the Treadmill
is
a doubly linked list, where each node is a piece of memory. The
words of each node,
|
[Forward
Link | Backward Link | Treadmill | Payload ----->]
|
The Treadmill object must not be moved. Depending on the
constructor argument, access to the instances may be synchronized.
This assumes that the implementation language, and the
language being implemented are the same. This works well with Jikes
RVM, as these are Java. However, for using with other VM
implementations in other languages, the doubly linked list class,
upon which Treadmill depends, should be rewritten.
If the created instance
is to be shared between the threads, which is decided by the boolean
parameter “shared”
provided as a parameter in the constructor, the access will be
synchronized with locks. A node is added to the treadmill during the
allocation, using addToTreadmill().
6.
Large Object Allocation
This is implemented in
LargeObjectLocal, which
extends the abstract class LargeObjectAllocator.
Each instance provides a fast unsynchronized access to the treadmill,
and bound to a single CPU. Hence this should not be shared across
different CPUs, as they provide truly concurrent threads.
Given c CPUs, and t Treadmill spaces, there will be c *
t instances of this class, for each {CPU, Treadmill} pair.
7.
Page Resource
Allocation of pages for
a space is managed by the abstract class PageResource.
When a space request a page, page budget and the use of
virtual address space are checked. If the request can not be
satisfied, garbage collection is triggered. MonotonePageResource,
which is a subclass of this class handles the monotonic space usage.
Similarly, the other sub class, FreeListPageResource handles
the ad hoc usage. Copying collectors allocate space monotonically
before freeing the entire space. Hence, MonotonePageResource is
useful for them. Though the MonotonePageResource is more restrictive,
it is easier to manage.
8.
Heap Growth Management
HeapGrowthManager
observes the heap utilization and GC load, and grows and shrinks the
heap size accordingly. This class, and all the other classes
in the package org.mmtk.utility.heap contains
the heap related mechanisms.
9.
Sanity Checker
Sanity checks for the
simple collectors are handled by the classes in the package
org.mmtk.utility.sanitychecker.
SanityChecker is the
major class handling the sanity checking. SanityDataTable
implements a simple hashtable to
store and retrieve per object information on sanity checks.
10.
Statistics
The package
org.mmtk.utility.statistics
contains a number of counters,
implementing the abstract class Counter for
multiple counting purposes. SizeCounter, aggregates
two EventCounter
objects, to count the
number of events and the volume. Xml class
writes the output in XML format.
11.
Deque
 |
| Classes extending Deque |
The package
org.mmtk.utility.deque defines
the doubly-linked, double-ended queue (deque). Though the double
linking slightly increases the space demand, this is a worth trade
off, as this provides an efficient buffer and operations such as
sorting.
LocalSSB implements
a local unsynchronized sequential store buffer. This is used in
critical code such as garbage collection work queue and the write
buffer used by many collectors. Hence, this is implemented as
efficient as possible in space and time. Each instance has a bump
pointer and a pointer to the sharedDeque. This class follows FIFO,
though it doesn't implement dequeing. TraceBuffer supports
enqueuing and dequeuing of tracing data and bulk processing of the
buffer.
12.
Log
Log class is
used for trace and error logging. Message buffer size is
intentionally kept large (3000 characters), as Lock class of
Jikes RVM logs a considerable amount of information during a
potential GC deadlock.
