Strange heap corruption error

Question

I am getting this eror from Visual C++:

HEAP[ShockRay3.exe]: Heap block at 00557018 modified at 00557044 past requested size of 24

This occurs when I add a line of code between two recursive calls in a function. All the line of code does is changes a pointer but for some reason every time I put it in, I get this error.

This is a simplified version of the code (only heap memory stuff an function calls)

int KDTree::BuildBranch(int height, Mailbox** objs, int nObjects)
{
    {...}
        //Check for termination
    if(height == -1 || nObjects < minObjectsPerNode)
    {
        {...}

        return nodeIndex - 1;
    }

    //Save this node's index and increment the current index to save space for this node
    BoundingBox* tempBox = new BoundingBox();
    //If this is first voxel, we don't keep track of stradle counts
    if(nodeIndex == 1)
    {
        {...}

        for(int i = 0; i < nObjects; i++)
        {
            //Get bounding box
            objs[i]->prim->MakeBoundingBox(tempBox);

            //Add mins to split lists
            xMins[index] = tempBox->x0;
            yMins[index] = tempBox->y0;
            zMins[index] = tempBox->z0;

            //Add maxs
            xMaxs[index] = tempBox->x1;
            yMaxs[index] = tempBox->y1;
            zMaxs[index] = tempBox->z1;
            index++;
        }
    }
    else
    {
        for(int i = 0; i < nObjects; i++)
        {
            //Get bounding box
            objs[i]->prim->MakeBoundingBox(tempBox);

            //Add mins to split lists checking for straddle
            if(tempBox->x0 < curVoxelBounds->x0)
            {
                {...}
            }
            else
            {
                xMins[xMinCount] = tempBox->x0;
                {...}
            }

            if(tempBox->y0 < curVoxelBounds->y0)
            {
                {...}
            }
            else
            {
                yMins[yMinCount] = tempBox->y0;
                {...}
            }

            if(tempBox->z0 < curVoxelBounds->z0)
            {
                {...}
            }
            else
            {
                zMins[zMinCount] = tempBox->z0;
                {...}
            }

            //Add maxs to split lists checking for straddle
            if(tempBox->x1 > curVoxelBounds->x1)
            {
                {...}
            }
            else
            {
                xMaxs[xMaxCount] = tempBox->x1;
                {...}
            }

            if(tempBox->y1 > curVoxelBounds->y1)
            {
                {...}
            }
            else
            {
                yMaxs[yMaxCount] = tempBox->y1;
                {...}
            }

            if(tempBox->z1 > curVoxelBounds->z1)
            {
                {...}
            }
            else
            {           
                zMaxs[zMaxCount] = tempBox->z1;
                {...}   
            }
        }
    }

    //If this is the root node, construct the scene bounding box
    if(nodeIndex == 1)
    {
        bb = new BoundingBox(xMins[0], xMaxs[nObjects - 1], yMins[0], yMaxs[nObjects - 1], zMins[0], zMaxs[nObjects - 1]);
        curVoxelBounds = new BoundingBox(xMins[0], xMaxs[nObjects - 1], yMins[0], yMaxs[nObjects - 1], zMins[0], zMaxs[nObjects - 1]);
    }

    {...}

    //Allocate space for left and right lists
    Mailbox** leftList = new Mailbox*[minLeftCounter];
    Mailbox** rightList = new Mailbox*[minRightCounter];

    //Sort objects into lists of those to the left and right of the split plane
    //Bounding box for left and right
    BoundingBox* rightBox = NULL;
    BoundingBox* leftBox = NULL;
    //Saved pointer to current bounding box
    BoundingBox* savedBox = curVoxelBounds;

    int leftIndex = 0, rightIndex = 0;
    {...}
    switch(axis)
    {
    case 0:
        for(int i = 0; i < nObjects; i++)
        {
            //Get object bounding box
            objs[i]->prim->MakeBoundingBox(tempBox);

            //Add to left and right lists when necessary
            if(tempBox->x0 < splitLoc)
            {
                {...}
            }

            if(tempBox->x1 > splitLoc)
            {
                {...}
            }
        }

        //Construct new bounding boxes
        leftBox = new BoundingBox(curVoxelBounds->x0, splitLoc, curVoxelBounds->y0,
            curVoxelBounds->y1, curVoxelBounds->z0, curVoxelBounds->z1);
        rightBox = new BoundingBox(splitLoc, curVoxelBounds->x1, curVoxelBounds->y0,
            curVoxelBounds->y1, curVoxelBounds->z0, curVoxelBounds->z1);
        break;

    case 1:
        for(int i = 0; i < nObjects; i++)
        {
            //Get object bounding box
            objs[i]->prim->MakeBoundingBox(tempBox);

            //Add to left and right lists when necessary
            if(tempBox->y0 < splitLoc)
            {
                {...}
            }

            if(tempBox->y1 > splitLoc)
            {
                {...}
            }

        }

        //Construct new bounding boxes
        leftBox = new BoundingBox(curVoxelBounds->x0, curVoxelBounds->x1, curVoxelBounds->y0,
            splitLoc, curVoxelBounds->z0, curVoxelBounds->z1);
        rightBox = new BoundingBox(curVoxelBounds->x0, curVoxelBounds->x1, splitLoc,
            curVoxelBounds->y1, curVoxelBounds->z0, curVoxelBounds->z1);
        break;

    case 2:
        for(int i = 0; i < nObjects; i++)
        {
            //Get object bounding box
            objs[i]->prim->MakeBoundingBox(tempBox);

            //Add to left and right lists when necessary
            if(tempBox->z0 < splitLoc)
            {
                {...}
            }

            if(tempBox->z1 > splitLoc)
            {
                {...}
            }

        }

        //Construct new bounding boxes
        leftBox = new BoundingBox(curVoxelBounds->x0, curVoxelBounds->x1, curVoxelBounds->y0,
            curVoxelBounds->y1, curVoxelBounds->z0, splitLoc);
        rightBox = new BoundingBox(curVoxelBounds->x0, curVoxelBounds->x1, curVoxelBounds->y0,
            curVoxelBounds->y1, splitLoc, curVoxelBounds->z1);
        break;
    };

    //Delete the bounding box
    delete tempBox;

    //Delete old objects array
    delete[] objs;

    {...}

    //Change bounding box
    curVoxelBounds = leftBox;
    //Build the left branch
    BuildBranch(height - 1, leftList, leftCount);

    //Change bounding box
    curVoxelBounds = rightBox; //<----THIS IS THE LINE RESULTING IN THE ERROR
    //Build the right branch
    int rcNodeIndex = BuildBranch(height - 1, rightList, rightCount);

    //Restore bounding box
    curVoxelBounds = savedBox;

    //Delete left and right bounding boxes
    delete leftBox;
    delete rightBox;

    {...}

    return thisNodeIndex;
}

If I take that line out where I change the pointer, the program works. If I leave it in, it doesn't work and the call stack shows this line:

delete[] objs;

but before that in the call stack is the line that seems to be causing this. I don't know how changing a pointer can jump the code to that delete line.

Answer 1

You might try Application Verifier. It's pretty good at finding memory overwrites and related problems.

Here is one bit of important information regarding Application Verifier. You can set full page heap validation. If your application has any heap overrun or underrun, it will be caught immediately. And it's extremely easy to use. And free.

Answer 2

Bug hunting can take days (and nights!). In such a big chunk of code it's not easy to find, and what you have posted in itself has no bugs. Neither will posting the whole code help, cause without the rest of the class we'd have to reimplement it to test it well.

However, what I can do is give you some pointers:

1. Reduce your crashing sample to the minimum -- in your case, load the least data to the KDTree that makes it crash.
2. NULL pointers after usage -- at least for testing purposes.
3. Use assertions -- Assert not-null before every pointer dereference.
4. Learn to use your compilers debugger, and do a step by step passthrough through the minimal sized example, especially taking a close look at curVoxelBounds

Answer 3

I can't see anything obviously wrong in the code you posted, however some of the omitted code may be relevant. So here's a few ideas to investigate:

• Are leftCount and rightCount being calculated properly so that they do not exceed their lists?
• Are leftList and rightList being properly filled with valid pointers?
• Wherever BuildBranch is called from the outside world, are the second and third parameters valid and correct?
• And is the outside world expecting the second parameter to be deleted by this function?

If those ideas don't get you anywhere, then a few questions:

• How many times has the function recursed into itself when the crash happens? Is it happening at the beginning or deep within?
• Is it possible to re-order the recursive calls so that right box is handled first and then the left box afterwards? If so, which one does the crash occur within when you try that?