Advertisement

Building a user space library for dynamic memory analysis

Amarender Barrenkala

July 14, 2009

Amarender BarrenkalaJuly 14, 2009

To ensure reliability of any embedded application which involves extensive usage of stack and heap, it is critical for the system designer to anticipate the maximum stack and heap utilization of the application during its lifetime.

Analyzing stack requirements is a rather straightforward and predictable process and hence most designers would prefer a scenario in which all the memory that would be required by the application is preallocated instead of dynamically allocating it.

Having said all this, there will be times when you would start seeing limitation of such an approach and would rather go for dynamic memory allocation. Even with dynamic memory allocation, reliability can be ensured provided a correct trending of the heap usage is done before freezing on the memory size.

Now, when it comes to dynamic memory analysis, there is one question that always comes to my mind, "Why does free() not return number of bytes freed?"

For the unaware here is the prototype:

void free (void *ptr);

By knowing the number of bytes freed, you could have easily tracked the growth trends of the dynamic memory for your application.The standard library maintains memory tables for tracking the malloc() and free() locations. To make the things simpler, we made a sample library having three functions:

1. hash_init()
2. insert()
3. eject()

These can be used in any environment, meaning in an OS based or a non-OS based environment. They won't add to development overheads once you understand them. At times, the same implementation might not directly work but the trick still holds true. Let me elaborate the method by taking up a case study.

Case-study
I have an application of around 10K lines code with hundreds of functions and thousands of function calls. Most functions use dynamic memory allocation and the function calls are randomly nested. In such a situation it is very difficult to track the maximum dynamic memory requirement (heap size) of the application.

Solution:
Based on the nature of the algorithm, I assumed that malloc() and free() calls are interleaved such that there are at most a hundred malloc() occurences for every free() call.

The idea is to use a hash-table initialized as global data (global initialized data is stored in .data section) of size 100. The hash-table stores the number of bytes associated with every pointer along with the corresponding pointer address.

I have the size information (in bytes) when I am allocating memory by calling malloc(). So, I will store this information in the hash-table every time malloc is called.

While freeing the memory associated with a pointer, I use the hash-table to retrieve the memory corresponding to every pointer. Alongside, I maintain a variable called peak_max_malloc which simply increments every time the heap grows due to malloc() call. At the end of the algorithm, this variable would indicate the maximum heap growth.

Usage:
* Initialization of hash table
* Insert() after every malloc() call
* Eject() after every free() call

The same technique discussed above has been practically applied to a hypothetical problem below. Let the program shown below represent a scenario where you would want to analyze the dynamic memory requirements. In its pure form the algorithm would look something what is shown in Figure 1, below.

Figure 1: Sample algorithm using dynamic memory

For above program, the maximum heap required can be calculated as,

MAX = 50*sizeof(some_structure)-(50*(50-1)/2)

Towards the end of the program, the heap again goes down to,

END = 49*sizeof(some_structure)

In a practical case, the occurrences of malloc() and free() calls would be spread over functions residing in different parts of the algorithm and probably located in different files.

By using these simple library functions insert() and eject() while dealing with dynamic memory, we would be able to accurately track the memory growth trends as well as detect memory leaks (if any) which might cumulate and lead to system failure over a period of time as shown in the Figures below.

Figure 2: Sample algorithm using the user space library for dynamic memory analysis

Figure 3: Hash table snapshot after executing line 9, after this max_heap_size is = 50*sizeof(some_structure)-(50*(50-1)/2)

Figure 4: Hash table snapshot after executing line 13, after this max_heap_size is = sizeof(some_structure)-49

Figure 5: Graph showing dynamic memory trends during the run-time of the program.

Now since we have clarity on the usage of these functions let us look at their implementation. To start with, the following are the functions we need to implement:

hash_init(): This function initializes the all the elements in hash-table with a DEFAULT value. The DEFAULT is used to identify an empty slot in the hash table. I used 99 as DEFAULT value assuming heap would never use this address range.

insert(): It searches an empty slot in the hash-table (i.e., row corresponding to DEFAULT value) and places pointer into first column and the size of memory corresponding to that pointer in the second column as shown in the above figure showing hash-table snapshots.

eject(): It searches for a pointer specified by the argument in the hash-table and if found, returns the size from the corresponding column of the hash-table. Post this, it reinitialises this row with the DEFAULT value indicating that the row is again empty and can be used by insert().

A sample program (heapcalc.c) showing usage and implementation of the above functions can be downloaded as a Zip file from the Embedded.com Source Code Upload/Download Archive.

The code attached has been tested thoroughly. A good practice would be to encapsulate these functions in your application with conditional macros so that once the memory analysis is done you can disable HEAP_CALC (#define HEAP_CALC 0) and get rid of the debug code.

Amarender Barrenkala is a Software Engineer in the Embedded Division of ThinkLABS. He has been working on architecting software for a re-programmable Robotic platform and embedded Linux based application development. He is also the owner of of project uNiBoard v1.1, an open source development platform for Embedded and Real Time Systems Programming. He can be reached at amarendermail@gmail.com.

Loading comments...