CArray pitfall

The Problem

CArray is one of my favorite classes. It's probably saved me more time than any other code I've used. Because it's such a popular piece of code, I imagined it had been used in every possible situation, and all the kinks had been worked out - so I was surprised when we stumbled onto this problem a few days ago.

Take a look at the following code and see if you can spot the bug:

CArray< int,int&> my_carray;

int some_number = 1;
my_carray.Add(some_number);

for(int i=0; i<=10; i++) {
    my_carray.Add(my_carray[0]);
}

TRACE("\nIndex\tValue");
for(int j=0; j<=10; j++) {
    TRACE("\n%d\t%d", j, my_carray[j]);
}

The TRACE output is:

Index Value
0 1
1 -572662307
2 1
3 1
4 1
5 -572662307
6 1
7 1
8 1
9 -572662307
10 1

Probably not what you were expecting.

Stepping into Afxtempl.h

A few snippets of code from Afxtempl.h will help show what's going on under the hood. We'll start by looking at the Add function:

AFX_INLINE int CArray< TYPE, ARG_TYPE>::Add(ARG_TYPE newElement)
{
    int nIndex = m_nSize;
    SetAtGrow(nIndex, newElement);
    return nIndex;
}

Nothing strange in the Add, it just calls SetAtGrow:

template< class TYPE, class ARG_TYPE>
void CArray< TYPE, ARG_TYPE>::SetAtGrow(int nIndex, ARG_TYPE newElement)
{
    ASSERT_VALID(this);
    ASSERT(nIndex >= 0);

    if (nIndex >= m_nSize)
        SetSize(nIndex+1, -1);
    m_pData[nIndex] = newElement;
}

Notice that SetSize gets called before the assignment of newElement when the if statement is true. Now look at the code for SetSize: (it's a big function - the interesting part is in bold near the bottom)

template< class TYPE, class ARG_TYPE>
void CArray< TYPE, ARG_TYPE>::SetSize(int nNewSize, int nGrowBy)
{
    ASSERT_VALID(this);
    ASSERT(nNewSize >= 0);

    if (nGrowBy != -1)
        m_nGrowBy = nGrowBy;  // set new size

    if (nNewSize == 0)
    {
        // shrink to nothing
        if (m_pData != NULL)
        {
            DestructElements< TYPE>(m_pData, m_nSize);
            delete[] (BYTE*)m_pData;
            m_pData = NULL;
        }
        m_nSize = m_nMaxSize = 0;
    }
    else if (m_pData == NULL)
    {
        // create one with exact size
#ifdef SIZE_T_MAX
        ASSERT(nNewSize <= SIZE_T_MAX/sizeof(TYPE));    // no overflow
#endif
        m_pData = (TYPE*) new BYTE[nNewSize * sizeof(TYPE)];
        ConstructElements< TYPE>(m_pData, nNewSize);
        m_nSize = m_nMaxSize = nNewSize;
    }
    else if (nNewSize <= m_nMaxSize)
    {
        // it fits
        if (nNewSize > m_nSize)
        {
            // initialize the new elements
            ConstructElements< TYPE>(&m_pData[m_nSize], nNewSize-m_nSize);
        }
        else if (m_nSize > nNewSize)
        {
            // destroy the old elements
            DestructElements< TYPE>(&m_pData[nNewSize], m_nSize-nNewSize);
        }
        m_nSize = nNewSize;
    }
    else
    {
        // otherwise, grow array
        int nGrowBy = m_nGrowBy;
        if (nGrowBy == 0)
        {
          // heuristically determine growth when nGrowBy == 0
          //  (this avoids heap fragmentation in many situations)
          nGrowBy = m_nSize / 8;
          nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);
        }
        int nNewMax;
        if (nNewSize < m_nMaxSize + nGrowBy)
            nNewMax = m_nMaxSize + nGrowBy;  // granularity
        else
            nNewMax = nNewSize;  // no slush

        ASSERT(nNewMax >= m_nMaxSize);  // no wrap around
#ifdef SIZE_T_MAX
        ASSERT(nNewMax <= SIZE_T_MAX/sizeof(TYPE)); // no overflow
#endif
        TYPE* pNewData = (TYPE*) new BYTE[nNewMax * sizeof(TYPE)];

        // copy new data from old
        memcpy(pNewData, m_pData, m_nSize * sizeof(TYPE));

        // construct remaining elements
        ASSERT(nNewSize > m_nSize);
        ConstructElements< TYPE>(&pNewData[m_nSize], nNewSize-m_nSize);

        // get rid of old stuff (note: no destructors called)
        delete[] (BYTE*)m_pData;
        m_pData = pNewData;
        m_nSize = nNewSize;
        m_nMaxSize = nNewMax;
    }
}

What happens is that m_pData gets deleted in SetSize, and when it returns to execute the line m_pData[nIndex] = newElement in SetAtGrow, newElement is a reference to the OLD m_pData that was just deleted!

Required Conditions

The problem only occurs when all three of the following are true:

1. The second parameter in the CArray template is a reference.
2. You call one of the following CArray functions and pass an existing array element as the newElement parameter:
   1. Add
   2. SetAtGrow
   3. InsertAt
3. Adding the element in 2) causes a memory allocation in the SetSize function.

Given all of these conditions, you're probably thinking this is a bit contrived. Actually it isn't. Although I cooked up the example code shown above, so I could demonstrate the problem, the genuine bug was found by running our application with a file that a customer had sent in because the application was giving incorrect results. We ran our application with BoundsChecker, and it found the CArray referencing a dangling pointer. Once this code was changed, the application worked properly.

Work-around

There are a number of ways to avoid/fix the problem:

• Don't use a reference as the second parameter of your CArrays. This is a good solution for small types such as int, but not very efficient for large structures.

  (i.e. CArray< int,int&> will cause the problem, but CArray< int,int> is fine.)

• Make a temporary copy of the element, and then add it to the array.
• Fix Afxtempl.h, so the assignment occurs before the delete (if you work at Microsoft).

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)