Devlog #1 – HeapHop and other memory chants

Posted by


A new music style has been created! I call it HeapHop! It’s the senseless shout a programmer does when he finds a pointer bug. Ever happened to you? It certainly has to me. Many times. And as C/C++ programmer I feel like it is going to be the song of my life. Luckily for me I have had it so many times that I decided to take action.

The problem(s)

  • Pointers that point somewhere that is not what it should be.
  • Unitiliazed memory, but you don’t know what it is, nor who allocated it.
  • Memory leaks. Don’t be shy, everyone forgets something time to time.

 

What we want #1 (Invalid pointers)

Output:

Integrity check
A block data [MySecondPotato; 0x000001B734B33980 (16 bytes)] has data similar to pointer [MyFirstPotato; 0x000001B734B33680 (16 bytes)] which has been deallocated
Offsets: [8;]

What we want #2 (Uninitialized memory)

Output:

Searching for: 00000000BAADF00D
Block 0000019753585040 [Size: 4, Offset: 0, Tag: MyFirstPotato]
0DF0ADBA

What we want #3 (Leaks)

Output:

Memory leaks detected
Leak: [000000000: 0000010F98223440-0000010F98223450 (16 bytes)]: MyFirstPotato

Our solution

We are approaching a release date (self imposed), and AccessViolation exceptions and runtime memory leaks are unforgivable. They must be eradicated.

For that I have tested a simple solution, to use a custom allocator, this allows us to keep track of what has been allocated, how many allocations have been done per frame, and how much heap are we using. This function has it’s downside of course, if we keep track of our heap we add some overhead. But I have considered it to be very low impact. At least I feel like it’s affordable. It could be used only for debugging and then disabling it for release.

Note this is not a pool, so I am not talking about cache coherency and the performance advantages it could take to allocate similar objects together.

In the classical way, we allocate an item and that’s it, we don’t store any information nor we keep track about that data.

If we are using a custom allocator we have some advantages, we keep track of:

  • Where has it been allocated?
  • When has it been allocated? Since it’s a game, and it’s supposed to run in realtime, we may want to decrease the amount of allocations per frame.
  • Has it been deallocated yet?

 

 

Now, the HeapHistory item that I have in the Engine is quite simple. I have an structure that stores this information, let’s call it AllocationInfo:

  • Bytes allocated: The amount of bytes that have been allocated. (Doh!)
  • MemoryTag: An optional ‘string’ that stores the user string describing where has the allocation been made. It could be the function signature or a custom string.
  • Id: And increasing numeric id, this identifies the allocation unequivocally.

Then came the decision of the container of this AllocationInfo. For my purpose I wanted fast search and fast insertion, so I decided to use std::map. There is probably (there always is) a better, faster way, but it seemed the least complex to implement, and we are on schedule :).

 

 

Now that we have that, I implemented some easy functions that allowed me to debug my heap state:

  • HeapDumpAllMemory: You want to see all the memory allocated. Useful if you want to see ALL the state of the game. Difficult to analyze, pretty to see.
  • HeapFindMatches: Now we are talking! This allows for detection of unitialized memory, if whenever we allocate something we set all the memory to 0xBAADF00D, this function let’s us search for memory patterns in all the heap we allocated, it’s slow, but it has definetely removed some bad habits.
  • HeapCheckIntegrity: Is there someone pointing to deallocated memory? Now this is something, at some point of the development I got to a point where I had some object that was pointing to some deallocated memory, but it wasn’t doing it anything with it until some action happened. (Sometimes arbitrary, since the gameplay cannot be predicted exactly). This keeps track of every tagged allocation (past or present). And checks in the current memory if any memory chunk has a pattern that matches the HeapHistory. It is very slow, but I thanks to this I have found some objects that were pointing somewhere that has already been deallocated.

Show me the code! 

Show here are some examples of my implementation. I created an std allocator to avoid circular allocations with the strings and the map. Also every data instantiation in here is in an anonymous namespace, so it is ‘static’, only visible to the current module. Don’t want anyone messing around with the allocator, only through exposed functions.

 

Now, general new and delete operators have been overloaded so that they call the HeapAllocate and HeapDeallocate:

The macros! Yes, I know, Preprocessor hell and all that, but I still haven’t found a useful replacement that may add the function signature.

Then, if for example we suspect that there is some object out there with invalid we could call,  HeapCheckIntegrity, which will dump suspicious memories.

Now, this may not be optimal, it doesn’t need to. But it is quite useful.

 

Space for improvement

There are many aspects in which we could improve the performance of this problem.

  • We could use pools and avoid more allocations.
  • More cache friendly allocations.
  • Faster containers
  • Faster check functions
  • Corruption check! We did not add any feature that checks patterns before and after the allocations to check if anyone is writing where it shouldn’t. (Although we may activate CRT and check with that)
  • Many things more I haven’t thought about.
  • Redudant thread safety (mutex vs atomics)

 

Webmaster Spelling Notifications

Leave a Reply

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