At the bottom is an example of how these tools may be used outside of the ECE 250 tester-driver environment.

ECE 250 students are not required to know this.

Memory management is tracked through the an overriding of the new, delete, new[], and delete[] operators. In order for the memory tracking to be as uninvasive as possible, it is necessary to override the global instances of the four operators. Each of these uses either malloc or free to allocate and de-allocate memory. In addition to memory allocation, it tracks information about the allocation in a hash table.

Memory Tracking

Memory allocation and de-allocation is tracked through a hash table.

Hash Function

The hash function is based on the address of the pointer being returned. Because almost all memory allocated with be 4 bytes in size (int and pointers (the testing machine is a 32-bit machine), we will ignore the two least-significant bits.

Information Stored

With each memory allocation, we must store certain pieces of information which allow us to correctly track what the student has done. We will store the following four fields:

void *address: The address of the first byte of the allocated memory.
int size: The number of bytes allocated.
bool is_array: Set to true if memory allocated with a call to new[] and false otherwise (new).
bool deleted: Has this memory address been deleted? Initially false.

The hash table class also stores two additional integers: int total_memory_allocated and int total_memory_deleted. Each time a new entry is entered into the hash table, the size is added to the first, while each time memory is de-allocated, the size associated with the address is added to the second.

The class member bool record, initially set to false may be used to either turn on or turn off memory tracking. This allows us to avoid tracking memory allocated and de-allocated by library functions such as cin. This variable may be appropriately set using:

void start_recording(): Begin recording memory allocations and de-allocations (set record = true).
void stop_recording(): Stop recording memory allocations and de-allocations (set record = false).

Two additional member functions document the memory allocated:

void summary(): This provide a brief summary indicaing the difference between the number of bytes which were allocated and the number of bytes which were deallocated. Thus difference must always be non-negative. This is printed to cout and a sample output is:
void details(): This provides a detailed summary of the number of bytes allocated, number of bytes de-allocated, and a summary of all memory locations. An example of such a report is given here:

`new` and `new[]`

Each time the operators new and new[] are called, the data is inserted into the hash table.

`delete` and `delete[]`

Each time the operators delete and delete[] are called, the data is not removed from the hash table, but rather, the deleted flag is set to true. This allows the student to summarize all memory allocations and deallocations.

Note: it may occur that de-allocated memory is reassigned by the operating system. In this case, the deleted flag is set back to false and the new information is recorded. This may create an inconsistency between the total number of bytes allocated and the sum of the bytes allocated with each individual memory allocation.

Background

For those interested, the overridden new operator is called with an argument (an unsigned integer) equal to the number of bytes requested. The new[] operator is called with an argument (an unsigned integer) eqaul to the total number of bytes required for the full array. The overridden delete and delete[] operators are called with a generic pointer argument (void *).

Observation

It is possible to override these operators within each class submitted by the students, however, it is felt that this would unnecessarily complicate the projects and would detract from the implementation of the data structures and algorithms. Even if they were provided with the classes, this would essentially duplicate code which students would use for each project.

Example

The following demonstates how you can use this memory tracking tool in any program. You can download the file example.cpp and the header file dwharder/Algorithms_and_Data_Structures.h. As well as demonstrating the functionality, this sample code gives three possible failures which may be the result of improper use of delete or delete[].

Program 1. Use of the dwharder/Algorithms_and_Data_Structures.h header for memory tracking.

#include "dwharder/Algorithms_and_Data_Structures.h"

int main() {
	// this allocation is not tracked
	int *x = new int[33];

        dwharder/Algorithms_and_Data_Structures::allocation_table.start_recording();
	// these are all tracked
	int *a = new int(3);
	int *b = new int[100];
	int *c = new int[1000];
        dwharder/Algorithms_and_Data_Structures::allocation_table.summary();
	delete a;
        dwharder/Algorithms_and_Data_Structures::allocation_table.summary();
	delete [] b;
        dwharder/Algorithms_and_Data_Structures::allocation_table.summary();
	delete [] c;
        dwharder/Algorithms_and_Data_Structures::allocation_table.summary();
        dwharder/Algorithms_and_Data_Structures::allocation_table.details();

	// Failure 1
	// int *z1 = new int[100];
	// delete z1;      // Wrong delete, use delete[]

	// Failure 2
	// int *z2 = new int[100];
	// delete [] z2;
	// delete [] z2;   // Deleting same memory location twice

	// Failure 3
	// int *z3 = (int *) 0x0F13AC79; // random address
	// delete [] z3;   // deleting memory not allocated

        return 0;
}

Memory Management and Tracking