|
eheap Part 2: Enhanced Debugging
by Ralph Moore, eheap Architect
August 2021
Introduction
Embedded systems are typically designed by small teams of engineers who have too much to do and need every bit of help they can get. Heap-usage problems can be difficult to find. The main ones are:
- Memory leaks due to blocks not being released when they should be.
- Overflows of buffers and stacks that damage the heap and neighboring chunks.
eheap is a new embedded system heap that provides special features to help debug these kinds of problems. eheap will run on any RTOS-based or standalone system.
This is the second in a series of three papers on eheap:
Heap Physical Structure
The previous configuration paper focused on the logical structure of eheap, which is comprised of bins. This paper focuses on the physical structure of eheap, which is comprised of chunks. Following heap initialization, eheap is structured as follows:
start chunk
donor chunk
top chunk
end chunk
The start and end chunks are inuse chunks with no data blocks; they mark the start and end of the heap space, respectively. All free space is initially contained in the donor chunk (dc) and in the top chunk (tc). These are free chunks. As explained in the configuration paper, the optional donor chunk is the source for small block allocations, and the top chunk is the source for all other allocations. Initially chunks are calved from dc or tc, then freed to bins, when no longer needed. Eventually chunk allocations should come almost entirely from bins.
Chunks
Each chunk has a header, and the remainder is available for use as a data block. Chunks are multiples of 8 bytes in size and they are aligned on 8-byte boundaries. eheap supports three types of chunks: inuse, free, and debug. The header is also referred to as the Chunk Control Block (CCB).
An inuse chunk is allocated by malloc(sz) and it looks like this:
forward link (fl)
backward link + flags (blf)
data block (>= sz)
The forward link is a pointer to the next chunk and the backward link is a pointer to the previous chunk. Since chunks are 8-byte aligned, the lower 3 bits of links are always 0 and thus can be used for flags. In this case, the bit 0 flag (INUSE) is set. The data block is used by application code and is at least as big as the requested size, sz.
A free chunk is freed by free(dp) and looks like this:
forward link (fl)
backward link + flags (blf)
chunk size
free forward link (ffl)
free backward link + flags (fbl)
bin number
free space
fl and blf are the same as the inuse chunk, except flags == 0. The chunk size is in bytes and includes the header + free space. The free forward and free backward links are used to link this chunk into the free list of the bin specified in the bin number field. The free space is available to be allocated. The header or CCB, as shown above, requires 24 bytes. This is the minimum chunk size supported by eheap – i.e. no free space. When a chunk is allocated by malloc(), the fields after blf are overwritten with the data block. Hence, the minimum data block size is 24 – 8 = 16 bytes.
A debug chunk is allocated by malloc(sz) when the heap debug mode is ON and it looks like this:
forward link (fl)
backward link + flags (blf)
chunk size
time
owner
fence
fences
data block (>= sz)
fences
fl and blf are the same as an inuse chunk, except bit 1 (DEBUG) is set in addition to bit 0 (INUSE). A debug chunk is a special kind of inuse chunk. The chunk size is in bytes and includes the header + data block + fences. The time field is the time when the chunk was allocated and the owner field is the task or LSR that allocated the chunk. A fence is a fixed word pattern, such as 0xAAAAAAA3. One fence is part of the debug chunk CCB. The other fences surround the data block and as many as desired can be specified.
Heap Debug Mode
Free, inuse, and debug chunks may be freely mixed in eheap. The heap debug mode determines if a chunk is allocated as a debug chunk (debug ON) or as an inuse chunk (debug OFF) when it is allocated by malloc() or realloc(). The debug mode can be turned ON or OFF by application software, thus allowing debug chunks to be selectively created. This is important because they often are much larger than inuse chunks.
For example, a programmer might want to surround a suspect data block with 10 fences above and below. Thus the debug chunk would be 40 + 40 + 24 - 8 = 96 bytes larger than an inuse chunk for the same size data block. Adding this much overhead to all inuse chunks could exceed memory available for the heap and thus not be feasible. Also, performance takes a hit because fences must be filled with the fence pattern when chunks are allocated. This might result in the system running too slowly to produce the problem being debugged or not running at all.
In a typical case, the addition of a new task to an already debugged partial system might result in heap problems cropping up unexpectedly. Debug mode can be limited to the new task, taskA, as follows:
void taskA_main(void)
{
smx_HeapSet(SMX_ST_DEBUG, ON);
smx_TaskHook(self, taskA_enter, taskA_exit);
while (1)
{
// task code
}
}
void taskA_enter(void)
{
smx_HeapSet(SMX_ST_DEBUG, ON);
}
void smx taskA_exit(void)
{
smx_HeapSet(SMX_ST_DEBUG, OFF);
}
When taskA first starts, debug mode is turned ON and entry and exit routines are hooked into the scheduler for taskA. When taskA is suspended or preempted, the scheduler automatically turns debug mode OFF via the hooked taskA_exit() routine. When taskA is resumed, the scheduler automatically turns debug mode ON via the hooked taskA_enter() routine. As a consequence, debug mode is ON when taskA runs and only when taskA runs. Thus, all chunks allocated or reallocated by taskA will be debug chunks and all chunks allocated or reallocated by other tasks will be inuse chunks.
Using Debug Chunks
Data block overflows are a common problem in heaps. Stacks overflow up (toward location 0) and buffers overflow up or down. When tracking down a buffer underflow or overflow problem, the number of fences on each side of the buffer might be quite large (e.g. 10 or 20) in order to see a signature that helps to locate the source of the problem. Note also that without large fences, one or the other CCB may be damaged and the system may stop running.
As discussed in the next paper (self-healing), the eheap scan function stops at chunks with broken fences so that they can be examined.[1] This can be done by setting a breakpoint on the FENCE_BRKN error reported by the heap scan function. Being able to do this is helpful because block overflows are often sporadic and difficult to repeat. Hence it may be necessary to allow the system to run for long periods before the overflow occurs.
Memory leaks can be found by scanning time and owner fields in debug chunks. In the first case, chunks older than a certain time might be suspect. In the second case, chunks owned by deleted or stopped tasks are suspect. For this type of sleuthing, fences around the data block would probably be eliminated so that debug chunk overhead vs. inuse chunk overhead would be 16 bytes rather than 96 bytes more. Then the net can be cast wider to cover more suspected chunks.
Chunk Fill Patterns
It often is necessary to look directly at a heap via a debugger memory window in order to figure out what is wrong. An additional debug aid offered by eheap is chunk fill patterns, which make this task much more pleasant and productive.
When fill mode is ON, malloc() fills the data block with the data fill pattern (e.g. 0xDDDDDDDD). This helpful both to identify inuse chunks and to see how much of an inuse chunk’s data block has actually been used. free() fills the free space of a chunk with a free fill pattern (e.g. 0xEEEEEEEE). The donor chunk and top chunk are filled with a DTC (donor & top chunk) fill pattern (e.g. 0x88888888), and of course, fences are filled with 0xAAAAAAA3.
These fill patterns really help to understand the heap image presented in a memory window. Old chunk headers are overwritten with the above patterns, so it is clear which chunk headers are actually in use and where chunks begin and end. In addition, it is helpful to see what memory is in use and what memory is free and to see dc and tc clearly delineated.
Fill mode, like debug mode, may be selectively turned ON or OFF. This is beneficial because filling chunks greatly reduces the performance of malloc() and free(). Therefore it is possible to enable filling only chunks of interest. Since such chunks are not likely to be in the same heap area, filling them helps them to stand out against the background of chunks not of interest. In addition, knowing what kind of CCB to expect helps to find and interpret it.
Error Checking and Reporting
eheap services check all parameters and report any that are not in their expected ranges and abort operation to reduce damage to the heap. In addition, links, flags, and fences are also checked by eheap services. Also heap scan functions (see part 3), if enabled to run, continually look for damage. These checks help to make debugging easier, by detecting problems before the system goes into the weeds.
Summary
eheap is a new embedded heap that has three types of Chunk Control Blocks (CCBs): free, inuse, and debug. It offers significant debug features, such as debug CCBs, chunk fill patterns, error checking, and trace functions, which are described in Part 3. These can be of great value in finding and fixing heap-usage bugs, which often are difficult to track down by other means.
Notes
[1] This is true only when debugging. In normal operation, the fence is fixed and the fix is reported.
Copyright © 2016-2021 by Micro Digital, Inc. All rights reserved.
eheap is a trademark of Micro Digital Inc.
back to White Papers page |
