flipCode - Tech File

flipCode - Tech File - Toby Jones [an error occurred while processing this directive]

Toby Jones
Click the name for some bio info

E-Mail: tjones@hot-shot.com

12/06/2000, Latest News And A Simple Memory Tracker

Wow, what an exciting month! At work, we're moving into crunch time. We have about three months to do six months worth of work. I'm responsible for some pretty important pieces of this project this time, and it will be exciting to get back into that code-until-you-drop mode.

Lately, I've been working with the release candidates of DirectX 8. Some very cool stuff is in there, and if you haven't checked it out, I highly recommend it, even if you are an OpenGL die-hard. I've recently posted my new DirectX 8 Graphics and Video tutorial on the net!

I've also done a lot of programming language research, much of it sparked by Tim Sweeney. And I have started on my new game engine. Like I said, what an exciting month.

Last time, I concluded with a play on a Sun Tsu statement, "If you know your compiler and you know yourself, you need not fear the outcome of a thousand battles." A very talented co-worker laughed at that statement. A few days ago, we were solving a tricky problem with asserts, and he was amazed that when I stopped program execution and double-clicked the entries in the call stack, my variables would change to whatever they were before they called the next function. Had he known this technique, he might have saved himself tons of time.

Not only do you need to know your tools, you need the right tools in the first place. I recently ran into a very tricky bug in DirectShow that was uncovered by the memory tracker I was using. A memory tracker is an invaluable tool, and I cannot understate how vital it is to good program development. One tool you can use is BoundsChecker. BoundsChecker is a great tool, but it is slow, and expensive, and inextensible. I don't have a tool like this for my own, so I'll build a crude one today. Please note that it is currently not thread safe, but it is reasonably extensible. If you want to use it, go ahead, as I'm putting it into the public domain.

Pointers are tricky. We want to be able to gracefully catch:

1) memory leaks due to dangling pointers,
2) crashes due to freeing bogus pointers,
3) NULL pointer deletion (not usually wrong, but it is sloppy),
4) bogus pointer access / NULL pointer access.

Overriding the standard memory allocation routines can catch the first three.

Using a smart pointer class can catch the last one.

I define a few things:


#define GlobalAllocPtr(x) DbgAlloc((x), __FILE__, __LINE__)
#define GlobalFreePtr(x) DbgFree((x), __FILE__, __LINE__)
#define malloc(x) DbgAlloc((x), __FILE__, __LINE__)
#define free(x) DbgFree((x), __FILE__, __LINE__)

I overload the operators new and delete:


inline void * operator new(size_t s, char * szFilename, int line) {
    return DbgAlloc(s, szFilename, line);
}

inline void operator delete(void * p) {
    DbgFree(p, NULL, 0);
}

#define new new(__FILE__, __LINE__)

and I create some memory allocation routines:


static inline void * DbgAllocRaw(size_t cbAlloc) {
    // Call the Win32 function to allocate the memory.
    // The funky syntax is required so that we call the _function_ and
    // not some overloaded macro.
    return (GlobalAlloc)(GMEM_FIXED, cbAlloc);
}

static inline void DbgFreeRaw(void * p) {
    (GlobalFree)(p);
}

Every time an allocation is made, I save the address in a linked list. When that memory is freed, I remove it from the list. If an allocation is made and not freed, or if unallocated memory is freed, then a note is made in a second linked list. When the program is done, it calls a routine to walk the lists. If the lists show that there were errors, then a dialog is displayed with the error type, and the file and line number that committed the error.

The linked list is pretty basic:


struct Node
{
    Node * pNext;       // next node, NULL if last node
    void * pMemory;     // memory to track
    char * szFilename;  // file name that made the allocation (or bug)
    int    iLineNumber; // line number of allocation (or bug)
    bool   fBugType;    // only used in bug list
};

// Two lists: an allocation tracker, and a bug tracker
static Node * g_pAllocList = NULL;
static Node * g_pBugList   = NULL;

As you can see above, memory is allocated using the DbgAlloc and DbgFree functions. These functions are never called directly. By using C's malloc/free or C++'s new/delete, these routines are called automatically.


void * DbgAlloc(size_t cbAlloc, char * szFilename, int iLineNumber) {
    if(0 == cbAlloc) {
        assert(0);
        // NOTE: If you get here, fix your code!
    }

    // Attempt to allocate the memory
    HGLOBAL hGlobal = DbgAllocRaw(cbAlloc);
    if(NULL != hGlobal) {
        // Track the allocated memory
        if(!ListInsert(g_pAllocList, (void *)hGlobal, szFilename, iLineNumber)) {
            DbgFreeRaw(hGlobal);
            hGlobal = NULL;
        }

    return (void *)hGlobal;
}

As you can see, an attempt is made to allocate memory, then the memory is inserted into the linked list. There is some extra error detection code thrown in there to make it a bit more robust.


void DbgFree(void * p, char * szFilename, int iLineNumber) {
    if(NULL == p) {
        // This is sloppy coding if you get here
        return;
    }

    // Find and free the node
    Node * fp = g_pAllocList;
    Node * rp = g_pAllocList;

    while((NULL != fp) && (p != fp->pMemory)) {
        rp = fp;
        fp = fp->pNext;
    }
    if(NULL != fp) {
        if(g_pAllocList == fp) {
            g_pAllocList = g_pAllocList->pNext;
        }
        else {
            rp->pNext = fp->pNext;
        }
        DbgFreeRaw(fp);
    }
    // Can't find node to free
    else {
        // NOTE: If you get here, fix your code!

        // Track the mis-freed memory
        ListInsert(g_pBugList, p, szFilename, iLineNumber, true));
    }
}

This code is a bit more complex, since it contains code to walk the linked list. This isn't great programming design, but the point is simplicity. It attempts to find the pointer in the list. If it finds it, it deletes it. If it can't find it, then it inserts a node into the bug list that marks a failure.

If you are worrying about memory trackers, you've probably seen a linked-list. Here is the code for the insertion. I assume you can either follow it or look it up in Sedgewick.


static bool ListInsert(Node * & pNode, void * x, char * szFilename, int LineNumber, bool fBugType) {
    bool fRet = true;

    do {
        // Handle no current list case
        if(NULL == pNode) {
            pNode = (Node *)DbgAllocRaw(sizeof(Node));
            if(NULL == pNode) {
                fRet = false;
                break;
            }
            pNode->pNext       = NULL;
            pNode->pMemory     = x;
            pNode->szFilename  = szFilename;
            pNode->iLineNumber = iLineNumber;
            pNode->fBugType    = fBugType;
        }
        // handle already in list case
        else if(pNode->pMemory == x) {
            fRet = false;
            break;
        }
        // handle everything else
        else {
            // Search for the insertion location
            Node * p = pNode;
            while((NULL != p->pNext) && (p->pNext->pMemory < x)) {
                p = p->pNext;
            }
            if((NULL != p->pNext) && (p->pNext->pMemory == x)) {
                fRet = false;
                break;
            }

            // Create the new node
            Node * pT = (Node *)DbgAllocRaw(sizeof(Node));
            if(NULL == pNode) {
                fRet = false;
                break;
            }
            pT->pNext       = p->pNext;
            pT->pMemory     = x;
            pT->szFilename  = szFilename;
            pT->iLineNumber = iLineNumber;
            pT->fBugType    = fBugType;
            p->pNext = pT;
        }
    } while(0);

    return fRet;
}

This code is fairly portable. The only routines that need replacing, so far, are DbgAllocRaw and DbgFreeRaw. The next function also needs to be rewritten to work on other platforms. Call this function just before you exit to track your errors. Make sure that you don't do any allocations after this or things might get horked.


void DumpMemoryStats() {
    if(NULL != g_pAllocList || NULL != g_pBugList) {
        DialogBox(NULL,
                  MAKEINTRESOURCE(IDD_MEMORYTRACKER),
                  NULL,
                  MemTrackerProc);
    }

    Node * pNode = g_pAllocList;

    // Delete the alloc list
    while(NULL != pNode) {
        Node * pT = pNode->pNext;
        DbgFreeRaw(pNode->pMemory);
        DbgFreeRaw(pNode);
        pNode = pT;
    }

    pNode = g_pBugList;

    // Delete the bug list
    while(NULL != pNode) {
        Node * pT = pNode->pNext;
        DbgFreeRaw(pNode);
        pNode = pT;
    }
}

This routine is simple in that it displays the dialog if needed, and then clears the lists. This last major function is the DialogProc, which takes the list information and displays it in a Windows ListView:


BOOL CALLBACK MemTrackerProc(HWND hwndDlg, UINT uMsg, WPARAM wParam, LPARAM lParam) 
{
    // Column definitions for statistic dumper.  These can be added to as needed
    static LVCOLUMN s_aCols[] = {
        { LVCF_TEXT | LVCF_WIDTH,                0, 4, "Error Type", sizeof("Error Type"), 0, 0, 0 },
        { LVCF_TEXT | LVCF_WIDTH | LVCF_SUBITEM, 0, 2, "File", sizeof("File"), 1, 0, 0 },
        { LVCF_TEXT | LVCF_WIDTH | LVCF_SUBITEM, 0, 4, "Line Number", sizeof("Line Number"), 2, 0, 0 },
    };

    switch(uMsg) {
        case WM_INITDIALOG: {
            HWND hwndDesc = GetDlgItem(hwndDlg, IDC_MEMORYDESCRIPTION);
            RECT rc;
            GetClientRect(hwndDesc, &rc);

            // Setup Columns
            for(int ix = 0; ix < sizeof(s_aCols) / sizeof(s_aCols[0]); ix++) {
                s_aCols[ix].cx = (rc.right - rc.left) / s_aCols[ix].cx;
                ListView_InsertColumn(hwndDesc, ix, s_aCols + ix);
            }

            // Display the remaining allocations
            Node * pNode = g_pAllocList;
            LVITEM item;
            ZeroMemory(&item, sizeof(item));
            item.mask       = LVIF_TEXT;
            item.pszText    = "Memory Leak";
            item.cchTextMax = sizeof("Memory Leak");
            for(item.iItem = 0; NULL != pNode; item.iItem++, pNode = pNode->pNext) {
                ListView_InsertItem(hwndDesc, &item);

                // Print filename and line number
                if(NULL != pNode->szFilename) {
                    ListView_SetItemText(hwndDesc, item.iItem, ++item.iSubItem, pNode->szFilename);
                    char szLine[16];
                    itoa(pNode->iLineNumber, szLine, 10);
                    ListView_SetItemText(hwndDesc, item.iItem, ++item.iSubItem, szLine);
                }
            }

            // Display the occurred bugs
            pNode = g_pBugList;
            item.iSubItem   = 0;
            for(; NULL != pNode; item.iItem++, pNode = pNode->pNext) {
                if(pNode->fBugType) {
                    item.pszText    = "Free Bad Memory";
                    item.cchTextMax = sizeof("Free Bad Memory");
                }
                else {
                    item.pszText    = "Smart pointer error";
                    item.cchTextMax = sizeof("Smart pointer error");
                }
                ListView_InsertItem(hwndDesc, &item);

                // Print filename and line number
                if(NULL != pNode->szFilename) {
                    ListView_SetItemText(hwndDesc, item.iItem, ++item.iSubItem, pNode->szFilename);
                    char szLine[16];
                    itoa(pNode->iLineNumber, szLine, 10);
                    ListView_SetItemText(hwndDesc, item.iItem, ++item.iSubItem, szLine);
                }
            }
            return TRUE;
        }

    }
    if(WM_COMMAND == uMsg && LOWORD(wParam) == IDCANCEL) {
        EndDialog(hwndDlg, TRUE);
        return TRUE;
    }

    return FALSE;
}

If you have never seen a DialogProc, this code can seem somewhat daunting. All it does is set up a ListView control and lists memory leaks, bad freeing, and smart pointer errors, which we discuss now. IDC_MEMORYDESCRIPTION is the ListView control ID.

A smart pointer is a pointer container that can behave like a pointer, but has the ability to trap errors. Here, I use a parameterized C++ class to act as a smart pointer.


template  class CP {
private:
    T * p;

public:

    CP() : p(NULL) {}
    CP(T * pt) : p(pt) {}
    CP operator=(CP cp) {
        // Allow assignment of NULL pointer
        if(NULL != cp.p) {
            DbgVerifyPtr((T *)cp.p);
        }

        // Make no attempt to guard against dangling pointer
        // here.  The memory tracker handles that.
        this->p = cp.p;
        return *this;
    }
    T operator*() {
        // Attempt to dereference if we are valid.
        // It may be invalid if loaded into this container then freed.
        if(DbgVerifyPtr((T *)p)) {
            return *p;
        }

        // Invalid pointer access (logged by DbgVerifyPtr)
        // Try to return gracefully
        return T();
    }

    // There may be a time you may need this.
    // However, it doesn't work for primitive
    // types, so we will ignore it for now.
    //  T * operator->() { return p; }

    void Delete(char * szFilename, int line) { DbgFree(p, szFilename, line); }
};

This class doesn't do much by itself. It will check if a pointer dereference is valid. A pointer is valid if it is in our tracker list. DbgVerifyPtr is the function that checks this. Before I give this routine, I will finish this smart pointer with a few macros:


#define P(type) CP<type>
#define DELETE_P(x) (x.Delete(__FILE__, __LINE__))

This wraps the creation and deletion of pointers. Under release builds these should be define as:


#define P(type) ((type) *)
#define DELETE_P(x) (delete (x));

If you need to allocate and free some memory, you might do something like:


int * p = new int(10);
delete p;

Under this new system, you would do:


P(int) p = new int(10);
DELETE_P(p);

And these will call the proper location depending on the build type.

Lastly, the DbgVerifyPtr function checks if a pointer is valid:


bool DbgVerifyPtr(void * p) {
    Node * pNode = g_pAllocList;

    // Search for the pointer
    while(NULL != pNode) {
        if(pNode->pMemory == p)
        {
            return true;
        }
        pNode = pNode->pNext;
    }

    // Track the mis-freed memory
    ListInsert(g_pBugList, p, NULL, 0, false));

    return false;
}

It walks the linked list and if it finds the pointer, it returns true. In about 400 lines of code, I won't have to worry much about memory bugs. I'd say that is one evening well spent. Its not as perfect as something like BoundsChecker, but it can be extended to track Windows heap memory, resources, or whatever. It also demonstrates, besides a few cool tricks, an easy way to track resources.

Except in the case of smart pointers, just code as you normally do. If you want to use a smart pointer, use the macro syntax to avoid having to do a lot of conditional code.

I'll probably refine as I go along. A nice thing about debug code is that it doesn't have to be perfect. It is meant to help the programmer. If it starts getting in the way more than it helps, I'll get rid of it. But its there for me (and now, everyone) to use.

-Toby

01/23/2001 - Why I Trust My Compiler
12/06/2000 - Latest News And A Simple Memory Tracker
09/21/2000 - Introduction

This document may not be reproduced in any way without explicit permission from the author and flipCode. All Rights Reserved. Best viewed at a high resolution. The views expressed in this document are the views of the author and NOT neccesarily of anyone else associated with flipCode.

[an error occurred while processing this directive]