Memory Allocation Quandary

Memory Allocation (and subsequent deallocation) is central to process management.  It is a very powerful mechanism.  But great power also comes with a cost.  Memory Allocation is easily abused and the results can be catastrophic. For the C programming language, Memory Allocation is performed by malloc() and free().

Processes are allowed to call malloc() and free() how often and when ever they choose. However, there are some dangers to avoid.

Mitigating Memory Allocation Performance

Firstly, malloc() is somewhat slow, and thus expensive.  For this reason, malloc() is usually avoided in high performance situations.  There are two ways to mitigate malloc() performance in such circumstances.

The first method is to create a local memory pool, created by a call to malloc() during process initialization.  Subsequently during run time, memory is allocated and freed from the local pool.

The second method is to define all memory requirements at process boot time; it then uses these requirements to preallocate all memory at boot time.  The result is that this method does not call malloc() and free() at run time.  It still leaves a problem: memory allocation is static and thus not dynamic.

Other problems with malloc() and free() include the Double Free Problem (a process calls free(x) and then mistakenly calls free(x) again), Memory Leaks (a process forgets to call free()), and Memory Starvation (malloc() fails due to a lack of free memory).

Tracking Solution

All of these problems can be avoided by tracking malloc() calls.  This is done by creating new versions of malloc() and free() (called malloc_() and free_()) that are front ends for memory allocation/deallocation).  The idea is to keep track of memory allocation by using the following data structure:

struct memory_chunk_
void*addr; /* address of return from malloc() */
uintsize; /* size of call to malloc() */
char*file_name; /* file name of malloc() caller */
uintline_number; /* line number in file of malloc() caller */
struct memory_chunk*next_chunk; /* next malloc() chunk */
struct memory_chunk_*memory_chunk;    /* linked list of malloc() memory */

malloc_() thus creates a struct memory_chunk_ and adds it to memory_chunk for every time it calls malloc().  And free_() checks if an address is in memory_chunk before calling free().

Memory_Chunk Solution

Now lets look at how memory_chunk solves our three problems.

In the Double Free Problem, a process calls free(x) and then mistakenly calls free(x) again.
The second call to free() would be prevented by free_(), since x is no longer in memory_chunk.

For Memory Leaks, a process forgets to call free() and the process eventually runs out of free memory. In this case, it is a very simple matter to summarize the linked list of memory chunks by sorting memory_chunk by file_name and line_number. The result will be a small number of malloc() calls that are the culprit.

And finally for Memory Starvation, malloc() fails due to a lack of free memory.  In this case, the problem might not be the result of forgetting to call free(), but rather the memory is over prescribed. Thus we want to know how all of the memory is used and are any of the allocations wasteful. Does all of the memory have to be allocated at this time?  What we want is to generate a report on memory usage sorting memory_chunk by file_name and line_number. This technique is obviously identical to the Memory Leaks problem.

So in conclusion, I have presented some dangers to using malloc() and free(). In addition, I have presented methods to deal with these problems.