Garbage collection in C-language code applications - Embedded.com

Garbage collection in C-language code applications

The C programming language is ideally suited for embedded systems. Itprovides low level control, portability, as well as structuredprogramming. However, it does not provide native garbage collection.

Many languages such as Java and C# support garbage collection sothat a developer no longer has to explicitly free memory. Once a blockof memory is no longer referenced by any pointers, the garbagecollector will automatically free the memory, preventing any memoryleaks.

The lack of a garbage collector could be considered a limitation ofC. However, it is possible to implement a trivial garbage collector ifwe are willing to live with a few limitations:

1. Instead of calling malloc() to acquire memory, callCollectMalloc(bytes, ptrCount).

2. All structures that have pointers to other structuresmust have the pointers at the top of the structure. This permits thegarbage collector to know which elements of a structure are pointers:

typedef struct Node {
  struct Node *next, *prev;   //must be at the top
  int value;
} Node;

3. When acquiring memory with CollectMalloc(bytes,ptrCount), the number of pointers at the top of the structure must bespecified in ptrCount.

4. All fixed root pointers such as head and tail pointersmust be registered by calling CollectRoot(&head).

5. The garbage collection function must be explicitlycalled.

With these limitations, a garbage collector can determine which datastructures are no longer referenced so that they can be freed. WhenCollectMalloc() is called, the garbage collector places an OBJECTheader above each requested block of memory:

typedef struct OBJECT {
  unsigned char magic;   //Contains 0x47
  unsigned char referenced;   //Is this objectreferenced?
  unsigned char ptrCount;   //Number of GC pointers inobject
  unsigned char index;   //Number of followed GC pointers
  struct OBJECT *next;   //Next object in linked list ofobjects
  struct OBJECT *prev;   //Previous object in linked list
} OBJECT;

The requested block of memory will be placed into a doubly linkedlist, and the number of pointers at the top of the block of memory willbe remembered.

When CollectGarbage() is called, all of the memory blocks will bemarked as unreferenced. Then all of the registered fixed root pointerswill be used to find the memory blocks that they reference. Each objectwill then recursively visit any other objects that it references. Eachvisited object will be marked as referenced. This is commonly known asthe “mark” phase of a garbage collector.

Next, any unreferenced objects in the linked list will be freed.This is commonly known as the “sweep” phase of a garbage collector.

A short example illustrates how this could be used:

#define TREE_NODE_PTR_COUNT 2
  typedef struct TreeNode {
  struct TreeNode _gc   *left,  *right;   //pointers at top
  int value;
} TreeNode;

TreeNode *top, *node0, *node1, *node2;

int main()
{
  node0 = (TreeNode*)CollectMalloc(sizeof(TreeNode),  TREE_NODE_PTR_COUNT);
  node1 = (TreeNode*)CollectMalloc(sizeof(TreeNode),  TREE_NODE_PTR_COUNT);
  node2 = (TreeNode*)CollectMalloc(sizeof(TreeNode),  TREE_NODE_PTR_COUNT);

  CollectRoot(&top);   //define a fixedroot node
  top = node0;
  node0->left = node2;

  CollectGarbage();   //frees unreferenced node1
  top = NULL;
  CollectGarbage();   //frees node0 and node2
  return 0;
}

This trivial garbage collector implementation enables the developerto focus on the algorithm and data structures instead of worrying aboutmemory leaks. The garbage collector could be improved by addingsemaphore protection to support multiple threads, and by placing anadditional magic value at the end of all allocated memory blocks tobetter detect heap corruption.

Steve Rhoads, PE , (MSEE) works at Thomson developing videoset-top-boxes. He is the author of the open source Plasma CPU projectwhich also includes a RTOS and TCP/IP stack at www.opencores.org/?do=project&who=plasma.You may reach him at rhoadss@yahoo.com .

(Editor's Note: The source code for Heap GarbageCollection in C is now available on the Embedded.com Source Code Archive. Registration is required for downloading the code.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.