Garbage in C
Garbage in C
The C programming language is a perfect fit for embedded systems as it provides low level control, structured programming, and portability. On the contrary, it does not provide any native garbage collection. Garbage collection is a mechanism that provides automatic memory reclamation for unused blocks of the memory. Developers and programmers dynamically allocate memory, but when a block is no longer needed, they do not return it to the system with a free() function call. Garbage collection considers such block by recognizing the unused memory and reallocates it back into the free memory area.
Garbage collection was introduced by John McCarthy in the year 1958 as a memory management mechanism of LISP language (List Processing Language). Other programming languages like Java, C#, python, and so on support garbage collection so that a programmer no longer has to free the memory explicitly.
There are numerous approaches to garbage collection, resulting in some families of algorithms, including reference counting and so on. Once a block of memory is no longer used or no longer referenced by any pointers, the garbage collector will automatically free the memory preventing the memory leaks. The lack of garbage collectors in C standard language is considered a disadvantage. Although it is possible to implement an insignificant collector if a programmer can accept some limitations such as:
- Call the function CollectMalloc(bytes, ptrCount) despite of calling malloc().
- All structures pointing to other structures must have the pointers at the top of structures. This will allow the garbage collector to know which elements of that particular structure are pointers.
E.g.:
typedef struct Node
{
struct Node *next, *prev; // should be present at the top
int value;
} Node;
- While acquiring memory with CollectMalloc(bytes, ptrCount), the number of the pointers at the top of any structure must be specified in the ptrCount.
- All fixed root pointers such as head and tail pointers must be registered by calling CollectRoot(&head).
- A garbage collection function must be explicitly called.
With these limitations, the garbage collector can determine the data structures that are no longer referenced so that they can be freed any time. When CollectMalloc() is called, a garbage collector places an OBJECTheader above each requested block of memory.
The requested block of memory will be placed into the doubly linked list, and the number of the pointers at the top of the block of memory will be remembered. When the function CollectGarbage() is called, all the memory blocks will be marked as unreferenced. All the registered fixed root pointers will be used to find the memory blocks that they reference to. Each of the object will then recursively visit other object that it refers. The each visited object will be marked as referenced. These are commonly known as the “mark” phase of the garbage collector. In the next step, if any unreferenced object in the linked list will be freed. This is called the “sweep” phase of garbage collector.
E.g.:
#include <stdio.h>
#include <conio.h>
#define TREE_NODE 2
typedef struct TreeNode
{
struct treeNode *left, *right // pointers at top
int value;
}treeNode;
treeNode *top, *node0, *node1, *node2;
int main()
{
node 0 = (treeNode*) CollectMalloc( sizeof (treeNode), TREE_NODE);
node 1 = (treeNode*) CollectMalloc( sizeof (treeNode), TREE_NODE);
node 2 = (treeNode*) CollectMalloc( sizeof (treeNode), TREE_NODE);
CollectRoot (&top); //defines a fixed root node
top = node0;
node0 -> left = node2;
CollectGarbage(); //frees the unreferenced node 1
top = NULL;
CollectGarbage(); //frees the node 1 and node 2
return 0;
}
The trivial garbage collector implementation enables a programmer to focus on the algorithm instead worrying about any type of the memory leaks. The garbage collector can be improved by adding some more protection to support multiple threads, and by placing an additional magic value at the end of allocated memory blocks to better detect the heap corruption.
The developers using C language think that the memory management is too important to be left to the computer while the LISP (List Processing) developers think memory management is too important to be left to the user. The main drawbacks of garbage collector that not knowing when an unused memory block actually is freed and if it ever will be. This has further consequences when the memory block is an object whose destructor is called at an unspecified time.