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).