Click here to Skip to main content
16,015,697 members
Articles / Desktop Programming / MFC
Article

CArray pitfall

Rate me:
Please Sign up or sign in to vote.
4.93/5 (17 votes)
27 Sep 2000CPOL 399.2K   32   39
This article describes how the CArray class can access deleted memory in certain situations

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

License

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


Written By
Software Developer (Senior)
Canada Canada
www.IconsReview.com[^]
Huge list of stock icon collections (both free and commercial)

The picture is from September 2006, after picking up a rental car at the airport in Denver, Colorado. I'm smiling in the picture, because I have yet to come to the realization that I just wasted 400 bucks ( because you don't really need a car in downtown Denver - you can just walk everywhere).

Comments and Discussions

 
GeneralMy vote of 5 Pin
Member 1041174228-Aug-14 6:04
Member 1041174228-Aug-14 6:04 
GeneralVote 5. Pin
HyunJin Moon10-Nov-12 21:09
HyunJin Moon10-Nov-12 21:09 
GeneralMy vote of 5 Pin
CarlJ1-Dec-11 22:43
CarlJ1-Dec-11 22:43 
Questionthanks Pin
osirisgothra7-Nov-11 12:05
osirisgothra7-Nov-11 12:05 
GeneralMy vote of 5 Pin
gordon8829-Oct-11 21:06
professionalgordon8829-Oct-11 21:06 
GeneralThank you!!! Pin
bioan20-Mar-08 19:03
professionalbioan20-Mar-08 19:03 
Generali always get error Pin
kelvin airstain21-Aug-07 18:25
kelvin airstain21-Aug-07 18:25 
GeneralI also met about the CArray's bug! Pin
taianmonkey4-Jan-07 20:54
taianmonkey4-Jan-07 20:54 
GeneralRe: I also met about the CArray's bug! Pin
Warren Stevens5-Jan-07 4:59
Warren Stevens5-Jan-07 4:59 
Generalhi Warren Pin
bagchisandeep11-Jan-06 5:29
bagchisandeep11-Jan-06 5:29 
GeneralRe: hi Warren Pin
Warren Stevens11-Jan-06 5:38
Warren Stevens11-Jan-06 5:38 
GeneralPassing CAray object to a function Pin
bagchisandeep11-Jan-06 4:56
bagchisandeep11-Jan-06 4:56 
GeneralRe: Passing CAray object to a function Pin
Warren Stevens11-Jan-06 5:06
Warren Stevens11-Jan-06 5:06 
NewsUse std::vector instead Pin
Warren Stevens8-Oct-05 5:21
Warren Stevens8-Oct-05 5:21 
GeneralCorrecting the class Pin
El Perro Azul7-Oct-05 12:52
El Perro Azul7-Oct-05 12:52 
AnswerRe: Correcting the class Pin
Warren Stevens8-Oct-05 5:01
Warren Stevens8-Oct-05 5:01 
GeneralPassing &amp; Returning CArray Object with function Pin
Renugopal19-Jun-05 21:07
Renugopal19-Jun-05 21:07 
i want to know how to pass CArray object to function and return the CArray
object from function...

Thanks
-Renugopal
GeneralRe: Passing &amp; Returning CArray Object with function Pin
Warren Stevens15-Aug-05 8:32
Warren Stevens15-Aug-05 8:32 
GeneralUsing CArray &lt;CRgn, CRgn&gt; Pin
Rajesh_Parameswaran3-Dec-04 23:12
Rajesh_Parameswaran3-Dec-04 23:12 
GeneralRe: Using CArray &lt;CRgn, CRgn&gt; Pin
Warren Stevens8-Dec-04 17:29
Warren Stevens8-Dec-04 17:29 
GeneralRe: Using CArray &lt;CRgn, CRgn&gt; Pin
Warren Stevens9-Dec-04 3:40
Warren Stevens9-Dec-04 3:40 
QuestionHow big is the size in CArray? Pin
Anonymous3-Dec-04 20:51
Anonymous3-Dec-04 20:51 
AnswerRe: How big is the size in CArray? Pin
Warren Stevens8-Dec-04 17:22
Warren Stevens8-Dec-04 17:22 
QuestionCArray problem?? Pin
owais31-Jul-03 20:06
owais31-Jul-03 20:06 
AnswerRe: CArray problem?? Pin
Warren Stevens5-Aug-03 16:16
Warren Stevens5-Aug-03 16:16 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.