Anna Becker
Software Engineer

Game Engine – Memory

The point of the second assignment was to use our heap system instead of the default. Where we can create multiple heaps to speed up allocation and reduce fragmentation. For instance if you have 1 heap for everything that will stay around the entire game, that data is not in the way when searching for other data or space to put more data. We also created tracking information for each piece of data and a redundancy in case of corruption.

The structure:
We had a memory singleton (Mem) that controlled everything. It contained all the information like the amount of heaps, amount of allocated data, and total size of allocations in bytes. In it was a pointer to the heap list and data doubly linked lists. The heap class points to the next and previous heaps and starts the data list. It also holds the amount and size of allocations for that heap.

The tracking class completes the data linked lists for both heap and mem as well holding tracking information. This part was tricky as it sits above the data and we return the pointer to the actual data on return, so how do you find it again? You store the pointer to the tracking block in the 4bytes above the data.

Windows system programming:
This was my first go with direct system calls and I’d be lying if it didn’t scare the fuck out of me. Though it was a lot easier and less dangerous than I feared. HeapCreate(), HeapDestory(), HeapAllocate(), HeapFree(), HeapRealloc(), HeapSize(), and overloaded new and deletes.

Problems:
The second call to HeapAllocate, I get “Windows has triggered a breakpoint in PA2.exe.” Awesome. Thanks for the helpful information. I write print statements, I degbug it every way I know how. The time to leave for yoga comes and goes. I’m too tunnel visioned to care. I even watch the memory: create heap, allocate heap header, allocate first block, and I see it go red as it attempts to allocate the next. And boom.

I’m not certain how, but eventually I notice that I’m not seeing the tracking head pointer being added. I type in the address of where it’s going, the memory window jumps way down. Oops. My pointer math was written incorrectly for calculating the end of the tracking block. Why is it always the little things that trip you up?

Sometime after delete started working, I started to get random crashes. And I mean random. With the same break point it would crash sometimes before and sometime not. When it’s difficult to reproduce, it’s even more frustrating to find what’s causing it. I’d fix it, move on, and it’d come back. All I knew was sometimes a pointer had issues. When do they not?

First I added the destroyHeap in the mem initialize method (only if there are some allocated from before) to clean up from previous tests. I figure if we are zeroing out everything else anyways, might as well make it nice and clean. Plus there might be a heap pointer going awry somewhere. That really just made it crash more. So I’d go back and forth with commenting it out and then using it again.

Then I added freeing the blocks in the heap before destroying the heap in order to clean up the global linked list. So really it was a continue on and see if that fixes the problem sort of situation.

In the end, I was debugging something else when I realized that fixing the global pointers in the heapFree function was acting unusual. Fixed it and no more random crashes. Then it was only a short time before I fixed the remaining unit test failures.

Some code:

void *Heap::privHeapAlloc(Align align, size_t inSize, char *inName,  int lineNum)
{
   int alignment = this->privGetAlign(align);
   TrackingBlock *head = this->TrackingBlockHead;
   size_t totalSize = inSize + sizeof(TrackingBlock)+alignment+1;
 
   //allocation of space
   void *unAlignedAddr = HeapAlloc(winHeapHandle, 0, totalSize);
 
   //check allocation
   assert(0 != unAlignedAddr);
 
   TrackingBlock *block = new(unAlignedAddr) TrackingBlock(inName,lineNum);
 
   Mem::privAddAllocInfo(inSize, block);
 
   //attach heap pointers
   if(head != 0)
   {
      head->hPrev = block;
      block->hNext = head;
   }
   this->TrackingBlockHead = block;
 
   //update allocation info
   this->privAddAllocInfo(inSize);
 
   //update block information
   block->allocSize = inSize;
 
   //get the address at the end of the trackingblock
   void *temp = (void*)((unsigned int)block + sizeof(TrackingBlock));
 
   void * p = (void*)((unsigned int)temp +(alignment - 1) & ~(alignment - 1)); 
 
   //write the address to the top in the 4 bytes above
   *((unsigned int *)((char*)p-4)) = (unsigned int)block;
 
   return p;
}

Leave a Reply

Your email address will not be published. Required fields are marked *