HnxGC - an accurate, pauseless & deterministic garbage collector

• Home
• Downloads
• Bookmark
• Contact

Programming Guide - Introduction

On This Page

Overview
Base Algorithm
Smart Pointers
Create a managed object
Define a managed class
Perform a collection
Object Model

Overview

HnxGC library works as a service provider that provides a set of functions (API) for application programs. To employ garbage collection, application program should call these API functions at the proper times and places, and be behaving correctly follow the principle of HnxGC architecture.

HnxGC only manages objects that are allocated via the HnxGC API, such as HNXGC_NEW / gcnew macros. These objects are referred as "managed objects" (have nothing related to managed object in Microsoft .NET platform). During the use of these managed objects, application program should keep the system properly informed about how these objects are referenced, so that the system can trace the graph of reference relationship to identify reachable and unreachable objects.

Knowing the basic idea of HnxGC algorithm may help programmers to develop correct and efficient C++ application with HnxGC library.

Base Algorithm

From the view of HnxGC system, every memory block in an application program's address space belong to either the "managed memory pool", or the world out-side the pool. "Managed memory pool" is a logical concept, and it is composed by all managed objects that were allocated via HnxGC API. Each managed object is an instance of C++ class. It may contain pointers to other managed objects. HnxGC system traces and *only* traces pointers in managed objects (the managed memory pool), it will never trace pointers outside the managed memory pool, such as pointers in the execution stack of application threads.

The world out-side the managed memory pool is referred as "root-set area" in HnxGC documentation. Data in root-set area are always considered as accessible from application program, and will never be reclaimed by the HnxGC as unreachable garbage. HnxGC only examines data structures in managed memory pool, will never touch out-side world, where you can create and use traditional C++ objects in any way you like without worry about the existence of HnxGC collector.

Any reference from out-side world (the root-set area) to managed objects should be properly cooperated with HnxGC system to let the system know which objects are accessible from application program. HnxGC uses reference counting to mark up managed objects that are directly referenced from root-set area, and will perform tracing collection starting from these objects - referred as "root objects". For example, if you are creating a new reference from root-set area to a managed object, you should inform the HnxGC system about that. HnxGC library provides a set of smart pointers and macros that can help you to do that and take care of the synchronization issue between application threads and garbage collector. For performance improvement, if you know you are using a managed object through an existing reference or just "moving" an existing reference within the out-side world, you may skip the report of reference change to the system. In general, effective changes of reference relationship between root-set area and managed memory pool should be properly reported to the HnxGC system as well as the changes of references within managed memory pool.

Smart Pointers

In the HnxGC header files, we provide a set of smart pointers that application programmers can use to replace their raw C/C++ pointers. By doing that, HnxGC system is automatically informed when reference relationship is changed, so that programmers need not to explicitly call low-level HnxGC API in their code.

Basically, there are three types of smart pointers in HnxGC corresponding to one type of pointer in C/C++. For example, the pointer to an instance of class "CFoo" in traditional C++ is of type "CFoo *", in HnxGC there are three different types of smart pointers that can point to the object. They are:

CLockedPtr<CFoo> - Objects pointed by this type of smart pointer will be treated as "root object" by the HnxGC system. This type of smart pointer should reside in root-set area. A pointer of this type represents a reference from root-set to managed objects. Typical usages include (1) automatic pointer variables in a function, (2) returning pointer value of a function, (3) OUT or INOUT type of function parameters, (4) static or global pointer variables of application program (in the data/bss section).

Note - by default, the CLockedPtr<> smart pointer use a "move" semantic on assignment between two CLockedPtr<> pointers. The source operand will lose the reference to the object after the assignment operation.

CMemberPtr<CFoo> - This type of smart pointer should *only* be a member pointer variable of a manage object. That is, it should *only* appear in a C++ class as the type of member variable. A pointer of this type represents a reference between managed objects.

CWeakPtr<CFoo> - A pointer of this type smart pointers can *NOT* hold the referent object alive. To prevent an object from reclamation by HnxGC system, application program need to have at least a pointer of either type CLockedPtr<> or CMemberPtr<> pointing to the object. A typical usage of CWeakPtr type smart pointer is as IN type parameter of a function.

For convenience of usage, you can use the synonyms of these smart pointers, as: lp<>, mp<> and wp<> for CLockedPtr, CMemberPtr and CWeakPtr. All these symbols are under the namespace "harnix".

Create a managed object

You can create a managed object based on a user-defined class, or based on a primitive type. Also, you can create an array of managed objects.

HNXGC_NEW / gcnew is designed for creating an object or an array of objects based on user-defined class. After declaring a user-defined C++ class with some requirement, which will be explained in later section, application program can use HNXGC_NEW /gcnew to create an instance in managed memory pool.

For example:

// create an instance of class CFoo in managed memory pool
CLockedPtr<CFoo> p = HNXGC_NEW CFoo;

// the same as above statement
lp<CFoo> p = gcnew CFoo;

// create a managed object with some initialization parameters
lp<CFoo> p = gcnew CFoo("pi", 3.1415);

// create an array of managed objects with 50 elements
lp<CFoo> p = gcnew CFoo[50];

You can use HNXGC_NEW_NATIVE / gcnew_native to create an instance or an array of a primitive type.

For example, you can create an integer object or an array of integers in managed memory pool as follows:

// create an integer in managed memory pool
CLockedPtr<int> p = HNXGC_NEW_NATIVE(int);

// the same as above statement
lp<int> p = gcnew_native(int);

// create an array of integers in managed memory pool
lp<int> p = gcnew_native(int)[50];

Define a managed class

HnxGC managed class are almost the same as the counterpart of traditional C++ class. They are all the same size, no extra base object or data structure are required. The difference is (1) pointers in traditional C++ class should be replaced by CMemberPtr<> smart pointers, (2) you should define a Traverse routine for the class, and (3) an optional OnReclaim routine for reclamation ordering control, etc.

For example, you can replace tradition C++ class member declaration statement

   CBar * m_ptr;

to HnxGC class member declaration

   mp<CBar> m_ptr;

To define a Traverse routine, you can use HNXGC_TRAVERSE macro as:

class CFoo {
     mp<CFoo>  m_pNext;
     HNXGC_TRAVERSE(CFoo) {
          HNXGC_TRAVERSE_PTR(m_pNext);
     }
};

In facts, the HNXGC_TRAVERSE macro defines the Traverse routine that HnxGC system will call. Thus, the HnxGC knows the CFoo object will reference another CFoo object when the system calls the Traverse routine.

If an object does not have any reference to other managed object, you can use HNXGC_ENABLE macro to define an empty Traverse routine, such as:

class CFoo {
	int i;
	HNXGC_ENABLE(CFoo)
};

You can use HNXGC_ONRECLAIM to define an optional OnReclaim routine that will be called by the system when the object is *going* to be reclaimed. When the system determines an object is unreachable and eligible for reclamation, it will call the OnReclaim routine to give the application the last chance to run. Application can request reclamation ordering in OnReclaim routine to guarantee some objects is alive when destructor is executed. Also, application program can resurrect the unreachable object back to alive again.

class CFoo {
    ...

    ~CFoo() {
       ... // destructor - runs when the object is reclaimed
    }

    HNXGC_TRAVERSE(CFoo) { ... }
or  HNXGC_ENABLE(CFoo)

    HNXGC_ONRECLAIM() {
        ... // runs before destructor of CFoo
    }
};

Perform a collection

During the execution of application program, when an object loses all references to it and becomes an orphan garbage, the HnxGC library will automatically reclaim the object. The OnReclaim and destructor routine of the object will be executed in turn, if the OnReclaim routine does not cause occur of resurrection.

If cyclic referenced objects become unreachable, i.e. there is no path from root-set area can reach these objects, these objects can be reclaimed by performing tracing garbage collection. Application program can use HNXGC_COLLECT() macro to request HnxGC library to perform tracing garbage collection. During the execution of HnxGC_COLLECT(), OnReclaim routines of unreachable objects will be invoked, and then the destructors of them (if no resurrection).

The ordering of execution of OnReclaim routines is undefined, but the ordering of execution of destructors will fulfill the requirement of ordering rules that is declared in the execution of OnReclaim routines. For example, suppose object A and object B become unreachable and are eligible for reclamation. If object A's destructor will access object B, i.e. object B must be alive before the completion of execution of object A's destructor, then application can do as follows. In the object A's OnReclaim routine, it can declare a dependence requirement that object B is depended by object A. When performing garbage collection, the HnxGC will automatically figure out a destructing ordering that guarantees object A is destructed prior to object B.

For multi-threading version of HnxGC, the destructor of an object may be executed in an application thread that drops the last reference to the object, or in the collector thread as the object is becoming orphan in a group of unreachable garbage. Therefore, in most cases, application should assume destructor will be executed in any threads of an application.

In addition to above methods of garbage collection, application program can mandatory destruct a live object using HNXGC_DELETE() call. The destructor of the object will be executed during the call. Application should hold an effective reference to the object before invoking the HNXGC_DELETE(), and should not access the destructed object after that (We recommend application program drop all references to the destructed object as soon as possible).

Object Model

When application progam invokes HNXGC_NEW/gcnew macro to create a managed object or an array of objects, the HnxGC system will return an address of a consecutive memory block. The size of the memory block is consecutive large enough to hold the requested object(s). The HNXGC_NEW/gcnew operator requires the caller provides class information, including the Traverse routine, etc. Instances of the class in an array are tighly packed as in traditional C++. We stores real instances of the class in array, not the pointers to objects in array (such as Java and .NET).

By this design, features like multiple inheritance, object composition, etc are supported in nature. An instance of a managed class can be stored as a member variable of another object, as base object, or as an element of an object array.

In HnxGC, we refer the address returned from HNXGC_NEW/gcnew as the address of a "Pouch". In most cases, "Pouch" is interchangeable with "object" or an instance of managed class. But, as we described above, pouch can contain one or more instances of a managed class. In the internal of HnxGC, the system only sees individuals of pouch and the class associated with pouch. HnxGC is tracing references between pouches instead between instance of managed class. Therefore, from the angle of the view of application program, an address of an instance of a class is not the same as the address of the pouch in many cases. For example, a traditional C++ pointer to an instance of a managed class may be pointing to the interior of a pouch, as it can be a field or base object of the outer pouch object, or as an element of the pouch object array.

HnxGC provides the concept of "interior pointer" that allows a pointer to the interior of a pouch. Application program can use the CLockedPtr<>, CMemberPtr<> and CWeakPtr<> smart pointers to reference an interior address of a pouch as well as reference the pouch. Several macros or inline functions, such as InteriorPointer(), are provided to manipulate interior pointer. You can convert a pouch with any interior address to an interior pointer and returned as CLockedPtr<>. For example, suppose class CFoo contains a field 'm_nData' of integer type. You can get an interior pointer by:

CLockedPtr<CFoo> pObj = gcnew CFoo; // create a pouch

// create an interior pointer and saved in `ptr'
CLockedPtr<int> ptr = InteriorPointer(&pObj->m_nData, pObj);

// drop the pointer to pouch
pObj = nullptr;

// Note: the interior pointer `ptr' will still hold the pouch alive.