Click here to Skip to main content
Click here to Skip to main content
Go to top

CArray pitfall

, 27 Sep 2000
Rate this:
Please Sign up or sign in to vote.
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)

Share

About the Author

Warren Stevens
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 PinmemberMember 1041174228-Aug-14 6:04 
GeneralVote 5. PinmemberHyunJin Moon10-Nov-12 21:09 
GeneralMy vote of 5 PinmemberCarlJ1-Dec-11 22:43 
Questionthanks [modified] Pinmemberosirisgothra7-Nov-11 12:05 
GeneralMy vote of 5 Pinmembergordon8829-Oct-11 21:06 
GeneralThank you!!! PinmemberIonut Codrut20-Mar-08 19:03 
Generali always get error Pinmemberkelvin airstain21-Aug-07 18:25 
GeneralI also met about the CArray's bug! Pinmembertaianmonkey4-Jan-07 20:54 
GeneralRe: I also met about the CArray's bug! PinmemberWarren Stevens5-Jan-07 4:59 
Generalhi Warren Pinmemberbagchisandeep11-Jan-06 5:29 
GeneralRe: hi Warren PinmemberWarren D Stevens11-Jan-06 5:38 
GeneralPassing CAray object to a function Pinmemberbagchisandeep11-Jan-06 4:56 
GeneralRe: Passing CAray object to a function PinmemberWarren D Stevens11-Jan-06 5:06 
NewsUse std::vector instead PinmemberWarren D Stevens8-Oct-05 5:21 
GeneralCorrecting the class PinmemberEl Perro Azul7-Oct-05 12:52 
AnswerRe: Correcting the class PinmemberWarren D Stevens8-Oct-05 5:01 
GeneralPassing &amp; Returning CArray Object with function PinmemberRenugopal19-Jun-05 21:07 
GeneralRe: Passing &amp; Returning CArray Object with function PinmemberWarren Stevens15-Aug-05 8:32 
GeneralUsing CArray &lt;CRgn, CRgn&gt; PinmemberRajesh_Parameswaran3-Dec-04 23:12 
GeneralRe: Using CArray &lt;CRgn, CRgn&gt; PinmemberWarren Stevens8-Dec-04 17:29 
GeneralRe: Using CArray &lt;CRgn, CRgn&gt; PinmemberWarren Stevens9-Dec-04 3:40 
QuestionHow big is the size in CArray? PinsussAnonymous3-Dec-04 20:51 
AnswerRe: How big is the size in CArray? PinmemberWarren Stevens8-Dec-04 17:22 
QuestionCArray problem?? Pinmemberowais31-Jul-03 20:06 
AnswerRe: CArray problem?? PinmemberWarren D Stevens5-Aug-03 16:16 

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

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

| Advertise | Privacy | Mobile
Web03 | 2.8.140926.1 | Last Updated 28 Sep 2000
Article Copyright 2000 by Warren Stevens
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid