Memory leak & invalid memory deallocation detection in the Linux kernel for modules using exclusively Operating System Abstraction Layer - Embedded.com

Memory leak & invalid memory deallocation detection in the Linux kernel for modules using exclusively Operating System Abstraction Layer

Memory leaks and memory corruptions are problems that can be easilyintroduced in code written in C or C++ and generally in any programminglanguage that does not have a garbage collector built in, causingsystem crashes and sometimes, even worse unexpected behavior, creatingbugs that are difficult to be detected.

In user space there are many open source projects that one can useto identify memory leaks and corruptions such as electric fence [6],its newer fork DUMA [7], and valgrind [8]. For coderunning in kernel context these tools are not available.

When the problems mentioned above end up as a “kernel panic” as theyoften do, there is no further ability for the engineer to inspect theoffending code other than to observe the stack trace. Also in kernelcontext, a memory leak is persistent: it will remain existent and mostprobably keep growing until a reboot, something that is unacceptable.

Kernel development allows direct access to the basic components andresources of the operating system, but debugging is not easy as the useof a debugger is not handy and one has to either use additional loggingor use advanced techniques such as using kernel debuggers like kdb[2][3] and kgdb [4] or use kernel patches such as the one provided byCatalin Marinas, described in [1].

In this article we will describe our methodology for identifyingmemory management problems for kernel modules that use Operating SystemAbstraction Layer (OSAL) without the need of extra patches or kerneldebuggers.

OSAL Fundamentals
The Operating System Abstraction Layer is a software layer that allowsengineers to develop applications that are OS agnostic [2]. It reducesthe porting complexity by providing an API for OS components such asthreads, synchronization and memory management allowing portability todifferent OSes provided there is implementation of the same OSAL andits API.

Figure 1 below shows theconcept of a typical software stack usingOSAL inside the kernel.

Figure1 ” The concept of using OSAL

Our  Methodology
This methodology has a a perqusite the presence of an OSAL. As shown inFigure 2 below , the header file needs to becompiled together with the source code of the kernel module so itprovides macros that replace the actual memory allocating/deallocatingfunctions with a call to the function itself and a log with usefulinformation about the memory address and size involved. Let us callthis header file OsalMemLeak.h.

The post processing script later on will parse all the logsgenerated by the macros and will analyze the data. It will match theallocations to the deallocations and determine if there is a memoryleak or memory corruptions created by code freeing memory buffers thatwere not allocated properly.


Figure2 ” Proposed Method

The header file
OSAL APIs need to be analyzed and a list of those that allocate or freememory need to be identified. The list needs to be further decomposedin the type of memory that they allocate/deallocate (memory buffer,thread, mutex etc).

Let us assume for the sake of an example the following APIs are thememory manipulating ones. This is would be just a subset of the wholeOSAL memory allocating/deallocating API, since except for memoryallocations and frees, also occurs for other OS components such asthreads, semaphores etc.:

void *osal_mem_alloc(int size)
void osal_mem_free(void *memBuffer)
int osal_mutex_init(*Osal_Mutex)
int osal_mutex_destroy(*Osal_Mutex)

After analysis a header file needs to be created. All the aboveidentified and classified APIs should be redefined in this header fileas macros.

Those macros, with the help of an inline function, as describedbefore, will call the original function to allocate/deallocate memoryand provide any functionality it was required to offer (for exampleallocate the buffer itself), and then log this to using the kernelfunction printk().

In order to get the minimum performance impact, the system should beconfigured so printk() does not print on the screen, only logs and doesnot ouput in STDOUT or STDERR). For example assuming a function:

void *osal_mem_alloc(int size)

This would correspond to the following macro:

#define osal_mem_alloc(memsize)
__osal_mem_alloc(memsize,__FILE__,__LINE__)

And there would be a definition of the inline function__osal_memAlloc() like this:

static inline void * __osal_mem_alloc(
                   UINT32 size,
                   char * filename,
                   int linenb)
{
    void * addr = (void*) osal_mem_alloc(size);

DPRINT_MEMLEAK(“MEM_DETECT_ALLOC:%p:%d:%d:%s:%d:%dn”,addr,size,OSAL_MEM_GUARD_A
LLOC_TYPE_MEMORY, filename, linenb ,current->pid);
        return addr;
}

For the sake of portability please note that the following macroneeds to be included:

#define DPRINT_MEMLEAK printk

This is done in order to cater for another operating system whereprintk() might not exist or not be a suitable logging solution. In thecase of Linux using printk() is safe for logging as it can be calledfrom any context and anytime. (For more details how printk() worksthe reader can refer to [5]).

Now let us assume the following snippet of code in an imaginarysnippet:

/* Declarations of the mutex and array of buffers */
Osal_Mutex myMutex;
Osal_Mem_Buffer *myBuffer[10];

/* Initialize the mutex i.e. allocate space for it */
if (osal_mutex_init(myMutex) !=
    OSAL_MUTEX_INITED_OK)
{
        return ERR_MUTEX_INIT;
}
/* Lock the mutex */
osal_lock_mutex(myMutex);

/* LOOP 1: Allocate memory for the 5 first buffers in thearray */
for (int i=0 ; i<5; i++)
{
        myBuffer[i] = (Osal_Mem_Buffer)
                               osal_mem_alloc(1024);
}
/* Allocations complete, so unlock the mutex
*/
osal_unlock_mutex(myMutex);
.
.
.
/* Lock again the mutex */
osal_lock_mutex(myMutex);

/* LOOP 2: Deallocate the 5 first buffers */
for (int i=0 ; i<5; i++)
{
        osal_mem_free(myBuffer[i]);
}

    /* Unlock the mutex */
osal_unlock_mutex(myMutex);
/* Destroy (free) the mutex */
osal_destroy_mutex(myMutex);

If the above code is compiled with the OsalMemLeak.h header file,the following example logs will be generated when the binary runs:

MEM_ALLOCATION:e2000000:4:2:/home/myuser/allocations.c:4:8423
MEM_ALLOCATION:e2abfe00:1024:3:/home/myuser/allocations.c:13:8423
MEM_ALLOCATION:e2ac0200:1024:3:/home/myuser/allocations.c:13:8423
MEM_ALLOCATION:e2ac0600:1024:3:/home/myuser/allocations.c:13:8423
MEM_ALLOCATION:e2ac0a00:1024:3:/home/myuser/allocations.c:13:8423
MEM_ALLOCATION:e2ac0e00:1024:3:/home/myuser/allocations.c:13:8423
MEM_DEALLOCATION:e2abfe00::3:/home/myuser/allocations.c:28:8423
MEM_DEALLOCATION:e2ac0200::3:/home/myuser/allocations.c:28:8423
MEM_DEALLOCATION:e2ac0600::3:/home/myuser/allocations.c:28:8423
MEM_DEALLOCATION:e2ac0a00::3:/home/myuser/allocations.c:28:8423
MEM_DEALLOCATION:e2ac0e00::3:/home/myuser/allocations.c:28:8423
MEM_DEALLOCATION:e2000000::2/home/myuser/allocations.c:31:8423

The post processing script
Complimenting the header file, the post processing script needs to bedeveloped to parse the log file (/var/log/messages) and match theallocations and deallocations based on the address, size and type.

If any address is allocated it must match a following deallocationof the same size and type. Similarly for any deallocation that happens,the script will need to match it with an allocation of the same sizeand type.

If any mismatches are found, the script will need to generate theappropriate message that there is a possible incorrectallocation/deallocation. For the above set of logs the script willmatch the memory allocations with the frees.

Assuming the condition that the first for loop (commented as LOOP1) changes and from i<5 becomes i<=5 instead, and keeping thesecond loop (commented LOOP 2) the same, a memory leak is induced andone extra log will be created:

MEM_ALLOCATION:osal_mem_alloc():e2ac1200:1024:3:/home/myuser/allocations.c:8423

The script will not match it with a free, causing an error messageto be produced.

Multithread warning
This methodology can have a pitfall in multithreading applications.

Assuming the above macro implementation of osal_mem_alloc() and asimilar for deallocation, a race condition can occur where theallocation in one thread can be preempted in this stage where theactual allocation occurred but before the logging occurs.

If at that stage the deallocation thread is called that completesbefore its own preemption. That would result to a proper allocationfollowed by a deallocation, but the logs of the deallocation will beappearing first, and followed by the allocation logs. This scenario isdisplayed in Figure 3 below :


Figure3 ” Logs in wrong order due to multithreading

A way to accommodate for this is to have the parsing script to checkthe PID in case of a deallocation preceding an allocation for the samememory address and type.

If the PID is the same it is definitely a malpractice and if theillegal free hasn't caused a kernel panic, the script should report itas an error. If the PID is different, the script can give out a warningfor a possible invalid free rather than an error.

Another possible solution is to statically define a lockingprimitive (such as a mutex) in the OsalMemLeak.h, and surround all theinline functions with that locking primitive.

Care in this case should be taken if there is a possibility ofsleeping or running in the context of an interrupt[9]. Also using thisprimitive will result to non-portable code. Although one obvious way torecover this is to log as soon as entering the inline function and thenhave extra logic in the script to determine what happened first, thisis a wrong approach.

Being preempted right after the first logging in the allocation andbefore doing the actual allocation cause the logs to appear in reverseorder than the events occurred in case the deallocation gets scheduledright after and completes before the actual memory allocation.

SEC4

Using the method as part of dynamic analysis
Our proposed method of identifying memory leaks and corruptions caneasily be used for dynamic analysis in a nightly build and/or testsystem. The production code can be built with the header file, and thenthe unit test binaries can be run to produce logs that can be analyzedfrom the post processing script.

The output of the script can be kept as a log and the script willreturn zero if no memory allocation warnings and/or errors were found,whereas  on the opposite case, it will exit with an error code.

Evaluating the results
Using the methodology described in this article, a header file needs tobe produced. It must replace functions that allocate and deallocatememory with macros that call the actual functions and log data such asmemory address and size.

Also, a Perl script that parses the logs generated by the binarywhen it runs, and analyzes the data producing alerts when possibleleaks and memory corruptions occur needs to be created. Thismethodology has a number of effects on the system being developed, bothpro and con:

Pros:
* Does not require any kernel patches or any special setup.
* Works efficiently in a virtualized environment which is one of themost common methods for debugging in kernel space.
* Suitable for RT Linux.
* Not hardware specific.
* Easily portable to any OS.
* Can easily integrate with unit tests and nightly build.

Cons:
* As described earlier in the earlier multithreaded implementation, athread that allocates memory, for example, can be pre-emptied beforelogging the allocation with the result that the de-allocation might belogged before the initial allocation.
* In case the logging needs to be disabled (for example when syslogdneeds to be disabled) there's no way to get the logs and further usethe script to debug.
* Negative (but very small) performance impact with the printk(). Mightbe crucial in some systems.

Future work
As a result of the work we have done so far, there are a number ofdirections we could go to extend its functionality, including:

* Add all the kernel functions in order to cover not only OSAL butalso software that uses kernel API as well.
* Extend the work for other operating systems.

Joseph Gasparakis is a senior software engineer workingfor Intel Corp. in Shannon,Ireland for the Performance Product Division of the Embedded ComputingGroup. He has a 9 year long work experience in telecoms industryworking on several proprietary and open source software stacks. He hasalso worked as system administrator, and he is a Certified EthicalHacker (CEH). Joseph is currently specializing in optimizations ofmulticore and network related technologies.

Rajalekha, Kilar Rajaram is working as network softwareengineer for Intel in Shannon, Ireland for the Performance ProductDivision of the Embedded Computing Group. She has extensive experiencein 3G and 4G wireless protocol stack development on a variety of realtime operating systems. She is currently focusing her energy in thedevelopment of Media Access Control layer for Wimax Base stations.

Mario Nicolas is a software engineer working for Intel,in Shannon, Ireland for the Performance Product Division of theEmbedded Computing Group. Having a mathematical background, his domainof expertise is the implementation and optimization of algorithms,including search, cryptographic and compression/decompression.

References
[1] http://lwn.net/Articles/187979/
[2] http://en.wikipedia.org/wiki/OSAL
[3] http://oss.sgi.com/projects/kdb
[4] http://kgdb.linsyssoft.com/
[5] Pichai Raghavan, Amol Lad, Sriram Neelakandan ” EmbeddedLinux System Design and Development ” paragraph 3.7.1, p. 81-82
[6] http://freshmeat.net/projects/efence/
[7] http://duma.sourceforge.net/
[8] http://duma.sourceforge.net/
[9] Jonathan Corbet, Alessandro Rubini, Greg Kroah-Hartman ” Linux Device Drivers” p. 121-123.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.