Method for detecting memory leaks in algorithm
Date of publication: 2013-12-14
I developed described method because available tools does not provide informations about memory allocation behaviour in
running program and i used it to solve memory leaks in real application during 2012-11 and 2012-12.
Part 1.
This document describes method for detecting memory leaks in application which does not leave allocated memory on application exit, but it makes memory leaks in its algorithm implementation.
Methods for detecting memory leaks in application are widely known and many methods was described. Special tools are available for detecting memory leaks, such as valgrind,
DevPartner from Borland Micro Focus and IBM Rational Purify. These tools are capable of getting informations about allocated memory on application exit and provides these informations to user.
Circular Buffer and Smart Pointer are known data structures. Description can be found for example here:
Circular Buffer: http://en.wikipedia.org/wiki/Circular_buffer
Smart Pointer: http://en.wikipedia.org/wiki/Smart_pointer
Clarification of application with algorithm type of memory leak
There are two general methods how application can release all its allocated memory on application exit:
1. Application uses wrapper for memory management functions and wrapper tracks allocated blocks of memory. If application exits, wrapper frees all allocated memory.
This can be made with one global instance of wrapper object in application, destructor of object is called on application exit.
2. Application uses some kind of smart pointer implementation.
Even with sophisticated memory management functions, application can make memory leaks in its algorithm.
Here is example of such application, titled "App". If architecture of application and its components is good or bad is not discussed in this document.
main()
{
CircularBuffer<SmartPointer> CB;
CircularBuffer<SmartPointer>::Index First;
CircularBuffer<SmartPointer>::Index Last;
CircularBuffer<SmartPointer>::Index CBIndexNone = NULL;
while (1)
{
for 100 iterations
{
Algorithm_With_Memory_Allocation(CB, &First, &Last);
}
Save_Data(CB, &First, &Last);
if some_condition
break;
}
}
Application "App" uses circular buffer CB which stores smart pointers containing pointers to allocated blocks of memory. Circular buffer object frees all its items in its destructor
and thus it frees all instances of smart pointer objects stored in it. This happens when program execution goes out of context in which circular buffer object CB is defined.
Let's say, function Algorithm_With_Memory_Allocation() contains implementation of algorithm which stores pointers to allocated blocks of memory to circular buffer CB. Algorithm
also modifies First and Last arguments so they points to items in circular buffer and marks start and end of valid data. Let's say, function Save_Data() saves data to somewhere,
it frees items from circular buffer and it modifies First and Last arguments so they points to items in circular buffer and marks start and end of valid data.
In case of correct implementation, after call of function Save_Data(), variables First and Last should have value CBIndexNone, thus marking circular buffer as empty, and all items in circular buffer
previously indexed with variables First and Last should be freed. Function Algorithm_With_Memory_Allocation() can start new processing and can allocate new blocks of memory and
store pointers to them into circular buffer.
Described application can have memory leaks in various places in function Algorithm_With_Memory_Allocation() or in function Save_Data(). For example, function Save_Data() can save only
part of data in circular buffer CB pointed by variables First and Last, but it can set variables First and Last to CBIndexNone, which results to growing circular buffer CB and making memory leaks.
However, when application exits, it releases all its allocated memory, because allocated blocks of memory are stored in circular buffer CB and application does not leave traces for memory tracking utilities.
Image with graph of memory allocation in real application, it shows memory leak 100kB in 5 minutes iteration. Application frees all of its allocated memory on exit.
Amount of leaked memory is calculated from memory allocation tracking informations.
Part 2.
For detecting memory leaks in algorithm, tracking application is used. Tracking application tracks all memory management functions in tracked application and saves informations into file.
Because tracking application should let tracked application to execute identically as if it was not tracked, tracking application should satisfy requirements:
1. It should be simple as possible and it should not contain computation expensive algorithms
2. It should not modify running application, it should not insert additional code to compiled application
3. It should not replace system provided memory manager
4. It should not modify allocated amount of memory
5. Amount of recorded data should be as low as possible
6. Recorded informations should allow to find name of source file and line in source file where block of memory was allocated
These requirements are mandatory, because tracked application can:
1. do really big amount of calls to memory management functions. In case when tracking application contains computation expensive algorithms, it can slow down execution of tracked application
2. be multithreaded and it can be sensitive to race conditions. In case of slowing down tracked application for example race condition can occur and tracked application can run into deadlock, or it can just stop working
3. modify or slow down its execution in case when some additional code is inserted into compiled application
4. depend on how system provided memory manager allocates memory
5. depend on boundaries and real size of allocated blocks of memory
6. do a lot of IO operations and if tracking application writes a big amount of data, it can slow down tracked application
Points (4) and (5) are maybe unlikely to occur, but if tracking application satisfies requirements, it can only be more usefull.
Tracking application contains two parts:
1. Memory allocation functions hooks
2. Simple MFC GUI application for processing recorded data