The testHash program provided with Purify to show you how to find and correct four types of memory access errors:
Reading uninitialized memory
Reading and writing beyond the bounds of an array
Reading and writing freed memory
Freeing unallocated or non-heap memory
If you have not yet built and run the testHash example program, do so now. For instructions, click
When a program attempts to perform an operation using values from uninitialized memory, the results can be unpredictable. The code often appears to work correctly until an unrelated part of the program changes, causing it to malfunction in mysterious ways. Purify calls this type of error an uninitialized memory read (UMR).
Expand the UMR line, then expand the putHash line.
Purify distinguishes between copying uninitialized data and using it in an operation. In this example, the program tests whether entry is non-NULL on line 135. Purify checks this access, and finds that entry contains uninitialized data. Purify reports a UMR error. The error is that ht[index] is not initialized before the copy to entry.
Notice, however, that Purify does not signal an error on line 134 when ht[index] is copied into entry. This is because it is common for correct code to copy uninitialized data, particularly when copying structures containing padding bytes used to align fields of differing sizes. For this reason, Purify does not report uninitialized memory copy (UMC) errors by default.
In this example, the code appears to work correctly when it is tested because the value of ht[index] is expected to be initialized to NULL. Since the memory in ht[index] has not been used, it happens to be NULL even without being initialized. The code is not correct, but appears to run correctly in the test cases. However, if new code is added later the program can produce incorrect results.
Here is another example:
int i;
int j;
j=i;
printf("%d",j);
In this example, i and j are not initialized. The value of i is copied to j so Purify marks j as uninitialized also. When the value of j is used as an argument to printf, Purify reports a UMR error. Purify actually detected a UMC error at j=i, however, by default Purify suppresses UMC error messages.
You can temporarily unsuppress the UMC messages in the testHash example by selecting Suppressed Messages in the View menu. For more information about how to suppress and unsuppress messages, click
To correct this error, you must determine where ht[index] should have been initialized. By looking at Purify's initial error message, you can see that putHash is called by testPutHash, which is called by main.
Click the Edit button in the message to open the source file.
Notice that ht is initially allocated in the function makeHashTable in hash.c.
hashtable* makeHashTable()
{
hashtable* ht;
ht = (hashtable*)malloc(HASHTABLE_SIZE*sizeof(hashEntry*));
return(ht);
}
The memory that ht points to is never initialized.
To correct this UMR error:
Add the
initialization code:
hashtable* makeHashTable()
{
hashtable* ht;
ht = (hashtable*)malloc(HASHTABLE_SIZE*sizeof(hashEntry*));
/* fix umr by initializing
all hash pointers to null */
memset(ht, 0, HASHTABLE_SIZE*sizeof(hashEntry*));
return(ht);
}
Recompile
the program and run it again.
Purify no longer signals an uninitialized memory read error on line
135 of hash.c. You have successfully corrected
a UMR error.
Reading before the beginning or after the end of an array uses data that is not intended to be used. If another part of the program writes to this memory, unexpected and incorrect values can be read and used. Similarly, writing beyond the bounds of an array can corrupt data used by other parts of a program.
Purify calls these types of errors array bounds read (ABR) and array bounds write (ABW) errors. Purify reports ABR and ABW errors when they occur, clearly indicating the origin of data corruption.
Expand
the first ABW line, then expand the putHash
line:
Use your debugger to verify that new_key is the overwritten array:
(dbx)
print new_key
new_key = 0x489a0 ""
To find the cause of the error, you must determine why the program is writing beyond the end of new_key.
Click the Edit button in the message to display the source file.
Look
at line 146 in putHash to see why it is trying
to copy into a string that is not long enough. The string new_key is allocated on line 145, just prior to
the strcpy.
The code attempts to create an array large enough to hold the string
in key by getting its length from strlen. The problem is that strlen
returns only the number of characters in the string key
and does not include the NULL character terminating
the string. When the NULL character is copied
into new_key by strcpy,
the program writes beyond the end of the array.
This error can cause intermittent failures. The malloc
function call returns memory blocks with sizes rounded up to a multiple
of 8 bytes. Most often, the NULL byte is written
into padding or alignment space with no adverse effect. Occasionally,
however, the write corrupts the adjacent memory. If that memory is used,
the error can result in serious consequences and noticeable symptoms.
Purify detects the error in every
case.
To correct this ABW error:
Add 1
to the value returned by strlen on line 145.
...
}
else {
old_value = NULL;
entry = (hashEntry*)malloc(sizeof(hashEntry));
new_key = malloc((strlen(key)+1)*sizeof(char)); /*
fix abw */
strcpy(new_key, key);
entry->key = new_key;
entry->value = value;
entry->next = NULL;
if (last_entry) {
last_entry->next = entry;
}
else {
ht[index] = entry;
}
}
...
Recompile
the program and run it again.
Purify no longer signals the ABW error. You have successfully corrected
an ABW error.
If your program makes an improper cast it can cause an array bounds error. Consider this code fragment:
void badCast(key)
void* key;
{
hashEntry* entry = (hashEntry*)key;
if (entry->value) {
...
If key is a pointer to a single malloc'd byte, the offset to value will go beyond the end of key. This causes an ABR error when the code refers to entry->value. The code is accessing memory illegally even if it does not appear to be running off the end of an array.
When a program frees a segment of memory, but continues to read from and write to that segment, the data in that segment is no longer protected. Another part of the program might allocate and start using this freed segment, change the data, and cause the program to crash mysteriously. Purify calls these types of errors Free Memory Read (FMR) or Free Memory Write (FMW).
It is not unusual to separate the use and freeing of memory. For this reason, Purify tells you not only where you read from freed memory, but also where you freed the block and where it was originally allocated. These operations are usually widely separated when two different modules pass data back and forth, and one module frees the other module's memory.
Failures due to FMR errors can be more intermittent than ABW errors. For example, if you add timer signals to your program—perhaps to update a program busy cursor—one out of 100,000 timer interrupts might occur between the free and the use of entry. If the handler code uses heap memory, it can reuse entry, corrupting it and causing intermittent behavior or a crash.
To facilitate finding FMR and FMW errors, Purify does not return freed memory for re-use as soon as it is freed. Instead, Purify puts the memory on a first-in, first-out free queue, returning it to the system only when the free-queue is full or when the system is out of memory. You can change the length of the free queue by using the -free-queue-length option.
Expand
the FMR line, then expand the remHash line.
The FMR message indicates that the program is reading from freed memory
in remHash.
The program is reading 4 bytes starting at 0x48948,
8 bytes into the freed block.
Use your debugger to verify that this is the freed memory:
(dbx) print
&entry->next
& entry->next = 0x48948
(dbx) print
entry
entry = 0x48940
The block of freed memory read is entry->next, and entry is the block
of memory that was freed; entry is a pointer to a hashEntry.
Note that you can also identify the free'd block
by looking at the allocation call chain. The message indicates that the
block was allocated in putHash, line 144.
The freed data is a hashEntry.
To find the cause of the error, you must find out why memory is being read after it has been freed.
Click the Edit button in the message to display the source file.
Look
at the function remHash. Notice that the order
of freeing the block and updating the pointers of the linked list is confused:
void* remHash(ht, key)
hashtable* ht;
char* key;
{
hashEntry* last_entry;
hashEntry* entry;
void* value;
int index = hashIndex(key);
for (last_entry = NULL, entry = ht[index];
entry && strcmp(entry->key,
key);
last_entry = entry, entry
= entry->next) {
}
if (entry) {
value = entry->value;
free(entry->key);
free(entry);
if (last_entry)
{
last_entry->next = entry->next;
}
else {
ht[index] = entry->next;
}
}
else {
value = NULL;
}
return(value);
}
To correct this FMR error:
Move
both of the free's so they occur after the
pointer updates.
if (entry) {
value = entry->value;
if (last_entry) {
last_entry->next = entry->next;
}
else {
ht[index] = entry->next;
}
free(entry->key); /* moved free to fix fmr */
free(entry); /* moved free to fix fmr */
}
.
.
Recompile
the program and run it again.
Purify no longer signals an FMR error. You have successfully corrected
this FMR error.
Confusion about memory ownership can lead to freeing the same memory several times, or freeing a block of memory that was never allocated. Purify calls these errors freeing non-heap (FNH) or freeing unallocated memory (FUM).
Expand
the FNH line, then expand the delHashTable line:
.
Use your
debugger to confirm that last_entry->value
is the same address that Purify reports as freed.
(dbx) print
last_entry->value
last_entry->value = 0xeffff764
To find the cause of the error, you need to determine why the program is trying to free the block on the stack.
Click
the Edit button
in the message to display the source
file.
Notice that the values inserted into the hash table are pointers to
the stack.
Look
at line 60 (shown in bold) in
delHashTable:
void delHashTable(ht)
hashtable* ht;
{
int index;
hashEntry* last_entry;
hashEntry* entry;
for (index = 0; index < HASHTABLE_SIZE; index++)
{
for (last_entry = NULL, entry =
ht[index];
entry;
last_entry =
entry, entry = entry->next) {
if (last_entry)
{
free(last_entry->key);
free(last_entry->value);
free(last_entry);
As the program goes through the hash table and frees each block, it
attempts to free the value that was put into the hash table. The block
of memory in line 60 does not belong to the hash table; it belongs to
the routine that uses the hash table to store this value.
It is not uncommon for ownership of memory to become confused between
modules, resulting in one module attempting to free the memory of another
module.
To correct this FNH error:
Remove
the incorrect call to free.
void delHashTable(ht)
hashtable* ht;
{
int index;
hashEntry* last_entry;
hashEntry* entry;
for (index = 0; index < HASHTABLE_SIZE; index++)
{
for (last_entry = NULL, entry =
ht[index];
entry;
last_entry =
entry, entry = entry->next) {
if (last_entry)
{
free(last_entry->key);
/* free(last_entry->value); removed
to fix fnh */
free(last_entry);
Recompile
the program and run it again.
Purify should not signal an FNH error at line 60 in delHashTable. You have successfully corrected this
FNH error.
To learn about finding memory leaks in the testHash program, click