Tracking and Reporting Allocation Information
When we left off at Part II, we'd developed a method for tracking the memory used by our program. The design delegates all tracking to two functions, which comprise most of the public interface of the memory tracking module.
Those functions are, of course, Mem::Allocate and Mem::Free. Although the interface is simple, there's actually quite a bit going on under the hood.
So let's jump in and see what these functions look like!
Taking a Look at Mem::Allocate
The Allocate function itself is quite simple, but it delegates all the dirty work to other functions:
void* Mem::Allocate(size_t size, MemType type){ void* ptr = InternalAllocate(size); TrackAllocation(ptr, size, type); return ptr;}Recall from Part II that MemType is an enumeration specifying which area of the code has allocated the memory; it's essentially a tag that lets us know where our memory is getting used.
That brings us to the InternalAllocate call. This is an internal call for the memory tracking module (i.e. nobody else should call it). InternalAllocate is essentially a wrapper for malloc, or _aligned_malloc, direct memory allocation calls to the OS, or any third-party allocator you might wish to use.
The function must obey two stipulations: it must never return a NULL pointer, and on any type of failure, it must throw an exception of type std::bad_alloc. (Side note: if you are not using exceptions in your code base, InternalAllocate should instead immediately commit suicide and kill the program.)
Aside from that, InternalAllocate and its implementation are entirely up to you, so I won't dig too deeply into it.
Next up we see a call to the TrackAllocation function. This function is also internal to the memory tracking module, but we will provide a public wrapper for it later on (recall in Part I we discussed the need for manually tracking memory for things like external libraries and so on).
The TrackAllocation Function
This is where things begin to get dirty. Remember in Part I we discussed various ways of actually storing the tracked allocations, and we settled on a bucket-sorted group of vectors. Here we encounter the usage of this data structure for the first time.
Before we look at the allocation tracker code, let's look at the support structures and variables:
// Trace this number of calls up the call stack. Be warned that increasing this number// will radically increase the overhead of the memory tracker, so tweak with caution.#define MEMTRACK_CALLSTACK_DEPTH 5struct MemTypeInfoRecord{ size_t MemoryAllocated; size_t MaxMemoryAllocated; unsigned NumAllocations; unsigned MaxNumAllocations; bool Watch; size_t Budget;};static MemTypeInfoRecord MemTypeInfo[MEMTYPE_ENUMSIZE];struct MemTrackRecord{ void* Address; unsigned LastAccessCallStack[MEMTRACK_CALLSTACK_DEPTH]; int Size; MemType MemoryType;};struct MemTrackBucketPage{ MemTrackBucketPage* NextPage; unsigned NumberOfEntries; MemTrackRecord* RecordArray;};static bool DiagnosticMode = false;static const unsigned NUM_BUCKETS = 4096;static const unsigned NUM_RECORDS_PER_BUCKET_PAGE = 16;static HANDLE MemTrackerHeapHandle = 0;static MemTrackBucketPage** MemTrackerBucketArray = NULL;static size_t MemTrackerOverhead = 0;#define MEMTYPEMACRO(typenumber, typestring) {typestring},static const char* MEMTYPENAME[] ={ MEMTYPEENUM};Most of this should be pretty self-explanatory; the rest we will cover later on. Now, let's see the actual TrackAllocation function:
static void TrackAllocation(void* allocaddress, unsigned allocsize, MemType memtype){ CritSecEntry cs; if(!MemTrackerHeapHandle) MemTrackInit(); MemTrackRecord* record = NULL; bool recordisoverwrite = false; UINT_PTR bucketindex = GetBucketIndex(allocaddress); MemTrackBucketPage* page = MemTrackerBucketArray[bucketindex]; if(!page) { page = AllocateMemTrackBucketPage(); MemTrackerBucketArray[bucketindex] = page; record = &(page->RecordArray[0]); } else { if(DiagnosticMode) { while(page->NextPage) page = page->NextPage; record = &(page->RecordArray[page->NumberOfEntries]); } else { while(page) { for(unsigned i = 0; i < page->NumberOfEntries; ++i) { if(page->RecordArray.Size < 0) { record = &(page->RecordArray); recordisoverwrite = true; break; } } if(record) break; if(page->NumberOfEntries >= NUM_RECORDS_PER_BUCKET_PAGE) { if(page->NextPage) page = page->NextPage; else { page->NextPage = AllocateMemTrackBucketPage(); page = page->NextPage; break; } } else break; } ASSERT(page != NULL); if(!record) record = &(page->RecordArray[page->NumberOfEntries]); } } ASSERT(record != NULL); record->Address = allocaddress; record->Size = allocsize; record->MemoryType = memtype; for(unsigned i = 0; i < MEMTRACK_CALLSTACK_DEPTH; ++i) record->LastAccessCallStack = GetCallStackPtr(2 + i); if(!recordisoverwrite) ++(page->NumberOfEntries); IncrementMemoryTypeCountNoMutex(memtype, allocsize); MemTypeInfo[memtype].NumAllocations++; if(MemTypeInfo[memtype].NumAllocations > MemTypeInfo[memtype].MaxNumAllocations) MemTypeInfo[memtype].MaxNumAllocations = MemTypeInfo[memtype].NumAllocations; if(MemTypeInfo[memtype].Watch) DebugLog("Allocated %u bytes of type \"%s\" at address %08x\n", allocsize, MEMTYPENAME[memtype], allocaddress);}Whew! That's a mouthful of code. Let's take it apart, from the top.
The first thing we do is enter a critical section. We do this to prevent re-entrancy problems when multiple threads want to allocate memory simultaneously. The critical section resource is managed by a simple RAII wrapper:
// Note that this assumes Windows/XBox plaform; adjust as needed for other platformsstatic volatile bool MemTrackCritSecInitialized = false;CRITICAL_SECTION MemTrackCriticalSection;static void MemTrackInitCritSec(){ // Note that on many platforms we must run a MEMSYNC instruction here before accessing a volatile variable if(!MemTrackCritSecInitialized) { // Again this is Windows/XBox specific; tweak for other platforms ::InitializeCriticalSectionAndSpinCount(&MemTrackCriticalSection, 4096); MemTrackCritSecInitialized = true; }}struct CritSecEntry{ CritSecEntry() { MemTrackInitCritSec(); ::EnterCriticalSection(&MemTrackCriticalSection); } ~CritSecEntry() { ::LeaveCriticalSection(&MemTrackCriticalSection); }};The next thing we do is check to see if the memory tracker table has been initialized, and if not, we initialize it. The initialization is pretty straightforward:
static void MemTrackInit(){ ASSERT(MemTrackerHeapHandle == NULL); ASSERT(MemTrackerBucketArray == NULL); MemTrackerHeapHandle = ::HeapCreate(0, 0, 0); const size_t allocsize = sizeof(MemTrackBucketPage*) * NUM_BUCKETS; MemTrackerBucketArray = reinterpret_cast(::HeapAlloc(MemTrackerHeapHandle, HEAP_ZERO_MEMORY, allocsize)); MemTrackerOverhead += allocsize; for(unsigned i = 0; i < NUM_BUCKETS; ++i) MemTrackerBucketArray = NULL; for(unsigned i = 0; i < MEMTYPE_ENUMSIZE; ++i) { MemTypeInfo.MemoryAllocated = MemTypeInfo.MaxMemoryAllocated = MemTypeInfo.NumAllocations = MemTypeInfo.MaxNumAllocations = 0; MemTypeInfo.Watch = false; MemTypeInfo.Budget = 0; } // Set up budgeting for all memory types here#define KILOBYTES(n) ((n) * 1024)#define MEGABYTES(n) (KILOBYTES(n) * 1024) MemTypeInfo[MEMTYPE_GENERAL].Budget = KILOBYTES(256); // And allocate budgets for the rest of your memory types here#undef MEGABYTES#undef KILOBYTES}Once we know everything is initialized and set up, we move on to the work of tracking the memory allocation. The first thing we do is find out which bucket we need to store the record in:
static UINT_PTR GetBucketIndex(void* address){ // We ignore the least significant 4 bits, as well as the most significant // byes, then shift down the remaining bits to obtain the index. We ignore // the low 4 bits in our engine since we allocate everything aligned to 16 // bytes, and therefore no important information is held in those 4 bits. // You may get better results by tweaking this code a bit. return (reinterpret_cast(address) & 0xfff0) >> 4;}Sidebar: Choosing Bucket Indices
I have to confess that I found the above method of index-calculation by a combination of experimentation and analyzing the patterns of which indices were used for which addresses. Unfortunately, I have misplaced the notes on how I arrived at the above code, so as far as this article is concerned, just accept that it is magic and it works very well [wink]
Once we know which bucket to work in, we see if a page has been allocated yet in that bucket. If not, we allocate one and use that; the allocation is done in, you guessed it, AllocateMemTrackBucketPage:
static MemTrackBucketPage* AllocateMemTrackBucketPage(){ const size_t allocsize = sizeof(MemTrackBucketPage*) + sizeof(unsigned) + sizeof(MemTrackRecord*) + (sizeof(MemTrackRecord) * NUM_RECORDS_PER_BUCKET_PAGE); MemTrackBucketPage* page = reinterpret_cast(::HeapAlloc(MemTrackerHeapHandle, HEAP_ZERO_MEMORY, allocsize)); MemTrackerOverhead += allocsize; page->NextPage = NULL; page->NumberOfEntries = 0; page->RecordArray = reinterpret_cast( reinterpret_cast<char*>(page) + sizeof(MemTrackBucketPage*) + sizeof(MemTrackRecord*) + sizeof(unsigned)); return page;}Note that this function does some address/pointer wizardry; this limits the portability a bit, but the effect is easy enough to reproduce on platforms where such address hacks don't work.
Now, what happens if we find a bucket that already has an allocated page? Our basic procedure is to search the linked list of pages until we find one with an empty slot, and then we store our record in that slot. If no available slots are found, we allocate a new page and tack it on the end of the linked list.
Sidebar: Diagnostic Mode
You may notice that when in "diagnostic mode" our procedure is a bit different. We will cover the significance of diagnostic mode in Part IV.
Once we have found a location to store our record in, it's a simple matter of setting the record's fields to the appropriate values, and then doing some statistics work. Notice that we can track the current number of allocations, the peak number of allocations, and the byte size of the allocations, all from this function. The majority of the stats go into the MemTypeInfo array, which is detailed above.
For the sake of simplicity (and the length of this article) we will leave the behaviour of GetCallStackPtr and the Watch flag until Part IV.
That leaves us with a single mystery function: IncrementMemoryTypeCountNoMutex. As the name suggests, this function is used to note that a memory type has had additional memory allocated in it. Further, it does not acquire/enter a critical section when it is called; we don't need to, because TrackAllocation already took care of that for us. We'll see more of this function in Part IV.
static void IncrementMemoryTypeCountNoMutex(MemType type, size_t amount){ MemTypeInfo[type].MemoryAllocated += amount; if(MemTypeInfo[type].MemoryAllocated > MemTypeInfo[type].MaxMemoryAllocated) MemTypeInfo[type].MaxMemoryAllocated = MemTypeInfo[type].MemoryAllocated; if(MemTypeInfo[type].MemoryAllocated > MemTypeInfo[type].Budget) Panic();}This code should basically explain itself. The one thing missing is the Panic function. In our implementation, this pops up a message box which allows the user to abort the game, enter the debugger, or turn off checks for budget overruns. It's up to you how you handle the budget overrun case.
The TrackFree Function
So, we've seen how to deal with allocations; what about when memory is freed?
void Mem::Free(void* memblock){ if(!memblock) return; size_t freedsize = TrackFree(memblock); InternalFree(memblock, freedsize);}Again, we delegate the work to two other functions. InternalFree is the counterpart of InternalAllocate and should simply do whatever it needs to do in order to free the block of memory.
TrackFree does the bulk of the interesting stuff, so let's see it:
static size_t TrackFree(void* address){ CritSecEntry cs; if(!MemTrackerHeapHandle) MemTrackInit(); UINT_PTR bucketindex = GetBucketIndex(address); MemTrackBucketPage* page = MemTrackerBucketArray[bucketindex]; ASSERT(page != NULL); MemTrackRecord* record = NULL; do { for(unsigned i = 0; i < page->NumberOfEntries; ++i) { if(page->RecordArray.Address == address) { record = &(page->RecordArray); break; } } if(record) break; } while((page = page->NextPage) != NULL); if(record == NULL) { ErrorMessage("WARNING - memory allocation was forgotten by the allocation tracker"); return 0; } if(record->Size == -1) ErrorMessage("WARNING - memory freed twice."); else { DecrementMemoryTypeCountNoMutex(record->MemoryType, record->Size); MemTypeInfo[record->MemoryType].NumAllocations--; ifMemTypeInfo[record->MemoryType].Watch) DebugLog("Freed %u bytes of type \"%s\" at address %08x\n", record->Size, MEMTYPENAME[record->MemoryType], address); } size_t recsize = record->Size; if(recsize < 0) recsize = 0; for(unsigned i = 0; i < MEMTRACK_CALLSTACK_DEPTH; ++i) record->LastAccessCallStack = GetCallStackPtr(2 + i); record->Size = -1; return recsize;}Once again, we enter a critical section and ensure that the tracker system is set up properly. Next we search the buckets for the correct record that corresponds to the address that is being freed. Aside from some housekeeping, we do two critical things: first, we call DecrementMemoryTypeCountNoMutex to adjust the count of allocated bytes; second, we do our best to discover error conditions, such as duplicate frees of the same memory, frees of records that we can't match, and so on. We'll cover this more in Part IV.
One final point of interest is that we return the size of the original allocation when we're done. This is handy in a number of ways, especially when working with third-party allocators that want to know the allocation size. Again, we'll wait until Part IV to get in depth with these features.
So let's see the DecrementMemoryTypeCountNoMutex function:
static void DecrementMemoryTypeCountNoMutex(MemType type, size_t amount){ ASSERT(MemTypeInfo[type].MemoryAllocated >= amount); MemTypeInfo[type].MemoryAllocated -= amount;}Couldn't be easier [smile]
Wrapping Up
We've now got the pieces for a robust and useful memory tracking system. However, we still haven't covered all of the goodies - there will be several interesting tricks we introduce in Part IV:
- Manual memory tracking for third-party libraries etc.
- Detecting duplicate frees and fixing them
- Obtaining call stacks to see where memory is being allocated
- Watching memory allocations/frees in realtime with debug logging
- Checking for buffer overruns
- And maybe some more if I think of anything!
Stay tuned!
Just kidding!
Great series of articles. I am definitely enjoying it. Thanks for putting in the time.