Some things seem like a good idea - and then there's the reality.

Using C/C++ means dealing with pointers. You can trick them up with smart pointers to reduce the chance of error, but sooner or later you're going to get memory leaks - little bits of memory you've allocated and never freed.

For software that needs to run for a long time reliably, these are death. You can watch the memory use of the process increase and increase over hours, days or weeks, until the server falls over.

To catch these, you need a system that can track memory use and help you find where the leaks are occurring.

Something else that is really useful, is a system to help you track when you stomp memory outside your allocated blocks.

I already had my own memory manager, so adding a memory tracker to it was straightforward because all allocations and frees were already routed through the memory manager. If you don't have a memory manager, you can override the default new/delete malloc/free in most modern runtime libraries to add these hooks yourself.

The memory tracker I implemented is deliberately simple. The major design criteria are that it has to be fast, and it can't rely on the memory manager. Memory use wasn't really an issue since I am working on PC where memory is more or less unlimited - at least in the development environment.

The system I implemented it is a giant hash table of pointers which point into to a giant static array of MemoryDebugBlockInfo structures. The hash table pointer array is two times the number of MemoryDebugBlockInfo structures to reduce collisions. Both of those arrays are allocated at startup so when an allocation or deallocation occurs, there is very little overhead. Free memory tracking blocks are linked together in a singly linked list which is set up during initialization, so to get a new block or free an existing one, it is one pointer change. The hash table is indexed using a DJB5 hash of the pointer returned by the memory manager, so lookups are quick and hash collisions minimal. It uses simple linear probing in the case of collisions. If a pointer doesn't exist in the table (a free with no allocation), it will search the entire table and then ASSERT.

To track memory stomps, each block gets small areas before and after each allocation which are set to known values which are checked when the block is freed to detect when the program has written beyond a block boundary.

The MemoryTracker interface:

    class MemoryTracker
    {
    public:
        MemoryTracker( void );
        ~MemoryTracker( void );

        // Called with full debug info for block being allocated
        void Allocating( MemoryDebugBlockInfo& block );

        // Called with mReturnedPtr to remove block on deallocation.
        void Freeing( const void *ptr );

        // Tag a memory block with file and line info.  Sometimes you want to tag allocations a little more specifically.
        void Tag( const void *ptr, const char *fileName, unsigned int line );

        // Print out a memory report, check all blocks for validity.
        void Report( void );
    private:
        static const unsigned int MAX_TRACKED_BLOCKS = 10000;   // Maximum number of blocks to track.  If block count exceeds this, MemoryTracker shuts down.
        unsigned int mUsedBlocks;                               // Number of memory tracker blocks in use
        unsigned int mHashTableSize;                            // Size of hash table (twice number of tracker blocks)
        unsigned int mBlockArraySize;                           // Size of block array - MAX_TRACKED_BLOCKS
        unsigned int mAllocations;                              // Total number of allocations processed
        unsigned int mFrees;                                    // Total number of frees processed
        unsigned int mMaxUsedBlocks;                            // Peak number of memory tracker blocks used
        sizet mMemUse;                                          // Memory use of memory tracker - this is big!
        MemoryDebugBlockInfo **mHashTable;                      // Array of pointers, most are NULL until a block is allocated and put into the hash table.
        MemoryDebugBlockInfo *mBlockArray;                      // Array of blocks.
        MemoryDebugBlockInfo *mFreeList;                        // Array of free blocks, singly linked list linked together by mReturnPtr as a 'next' pointer
        bool mDisabled;                                         // True if memory tracking is temporarily disabled
        Spinlock mLock;                                         // Spinlock to protect access to memory tracker data
    };

Every block allocated stores this information:

struct MemoryDebugBlockInfo
{
    char mFileName[ FILE_NAME_SIZE ];           // Name of file where allocation occurred
    fourcc mPool;                               // four character code name of module which allocated block.
    byte *mBlockPtr;                            // Pointer to start of allocated memory manager block
    sizet mBlockSize;                           // Size of allocated memory manager block
    byte *mReturnedPtr;                         // Pointer returned by new/malloc
    sizet mAllocatedSize;                       // Size of allocated memory (header + block)
    sizet mHeaderSize;                          // Header size before mReturnedPtr
    byte mDebugSuffixSize;                      // Size of known value block suffix for overwrite detection
    byte mDebugPrefixSize;                      // Size of known value block prefix for overwrite detection
    bool mStartupAllocation;                    // If block was allocated before start of main()
    uint16 mLine;                               // Line of file where allocation occurred
    uint16 mCrc;                                // CRC of this data, used to verify validity of memory tracker data
    OS::Time::timevalue mTime;                  // Time of allocation
}

The current system produces some simple statistics which include the total number of allocations/frees and peak number of allocations.

The main report is split into two parts, the first is normal unfreed blocks allocated after main starts (my memory manager has a toggle to track that.) This first report is what to look most closely at and use to track down the memory leaks in the program. I added an assert when there are blocks in this report so it is obvious when I add a bug to the code.

The second report is those blocks that are allocated as part of the startup of the program. These are globals and statics which are initialized before main starts. This lets you keep an eye on your overhead.

MemoryTracker Report
Allocations: 203068 Frees: 203024
Tracking 44 blocks, 9956 available.  Peak used blocks was 2215.  Tracker using 781K RAM.
Address Size[BlockSize] (File:Line) Pool
========= Normal ==========
2063912 1484[1548] includenetworkgenericpacket.h(16) dflt ............test................ B0DA800000000000050000007465737400A3A3A3A3A3A3A3A3A3A3A3A3A3A3A30
2082256 1484[1548] includenetworkgenericpacket.h(16) dflt ............test................ B0DA800000000000050000007465737400A3A3A3A3A3A3A3A3A3A3A3A3A3A3A30
...
========= Startup =========
39341016 6[70] braryutilitysourcestring.cpp(193) dflt n.A.n. 6E0041006E000
39341152 6[70] braryutilitysourcestring.cpp(193) dflt I.n.f. 49006E0066000
...
Tracking 44 blocks, 9956 available.  Peak used blocks was 2215.  Tracker using 781K RAM.

The report also prints out the ascii and hex values of the first 32 bytes of the memory block - sometimes knowing where it was allocated doesn't help you quite enough when there are tens of thousands of allocations at a given location and only one or two are going wrong.

Originally I supported 500,000 blocks with 39MB of RAM, I've since reduced that since I don't have near that many blocks yet. I had a loop go awry which allocated all of those 500,000 blocks and it took almost 10 minutes to generate the report which left me scratching my head a bit as to what was going on when the report started then appeared to stop before listing the bad blocks.

There are still some things I still plan to add to the system:

• I'd like to track the total number of allocations and the peak number of simultaneous allocations for different block sizes: 8, 16, 32, 64, etc. plus blocks larger than 65536. That is handy for figuring out if you can make better use of your memory by allocating larger blocks per allocation.
• I'd like to make a bitmap of the memory map, colored based on the age of the block, to see how memory is used over the lifetime of the program.
• I'd like to be able to track memory usage by type. All of my allocations have a fourcc so I can track which systems are using which memory. This would also make a nice bitmap report.

So why is it a dratted memory checker? Well, the first time I ran it, it came up with about a hundred unfreed blocks. Lots of those were simple to fix - I wasn't shutting down a couple of major systems before running the memory tracker report. But once the easy ones were knocked off, even with tools like this, tracking down memory leaks can be a tricky thing, and it took me a couple days to find the causes of the 5 or so legitimate leaks in my code and fix them.