Declarative 'meta-stack' Garbage Collection in the C programming language
Original Publication Date: 2002-Jan-13
Included in the Prior Art Database: 2003-Jun-20
Successful memory management in the C programming language is notoriously difficult. Accessing previously released memory or omitting to release memory are hazards that every C programmer seeks to avoid. In simple projects, problems of this sort can be avoided by clear design, rigorous code review and unit testing. However, as programs become more complex, it is increasingly difficult to keep track of the 'owners' of pieces of memory. Memory allocated in one part of the program may be used in several other modules; which modules use the memory may vary according to the actual path taken through the code. It can be very difficult for the "last user" of a piece of memory to realise they are the last user and that they must free it. If it becomes too difficult (or even provably impossible) to manage memory manually, a collection of techniques known collectively as "garbage collection" are often employed. The general approach is to periodically determine which blocks of memory are no longer accessible and return them to the pool. Techniques include reference counting and "mark and sweep". However, C allows pointers to be 'disguised'. This means that garbage collectors may incorrectly identify memory as garbage when it is not. Worse still, some implementations may require that any process-wide memory allocation data structures be locked during this processing: effectively stopping the running of the program for unpredictable durations at inconvenient times. Furthermore, garabage collectors are, in general 'dumb' they are unable to capitalise on domain-specific information that could enable optimisations to be performed. Finally, they are slow: computation power is required to determine which memory areas are suitable for release. The invention described in this disclosure is applicable to the large class of programs that can be characterised as "stateless message processing" applications. Examples are HTTP servers and products such as IBM's MQSeries* Integrator. These products take a message as input, process it and output a response (or responses) at which point they "forget" about the previous transaction and revert to their previous state before accepting the next message. Since no state is maintained between iterations, any memory allocated by the program during one of these iterations should be released by the end.