Click here to Skip to main content
11,631,992 members (73,324 online)
Click here to Skip to main content

CArray pitfall

, 27 Sep 2000 CPOL 160.7K 32
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).

You may also be interested in...

Comments and Discussions

 
GeneralMy vote of 5 Pin
Member 1041174228-Aug-14 6:04
memberMember 1041174228-Aug-14 6:04 
GeneralVote 5. Pin
HyunJin Moon10-Nov-12 21:09
memberHyunJin Moon10-Nov-12 21:09 
GeneralMy vote of 5 Pin
CarlJ1-Dec-11 22:43
memberCarlJ1-Dec-11 22:43 
Questionthanks Pin
osirisgothra7-Nov-11 12:05
memberosirisgothra7-Nov-11 12:05 
GeneralMy vote of 5 Pin
gordon8829-Oct-11 21:06
membergordon8829-Oct-11 21:06 
GeneralThank you!!! Pin
Ionut Codrut20-Mar-08 19:03
memberIonut Codrut20-Mar-08 19:03 
Generali always get error Pin
kelvin airstain21-Aug-07 18:25
memberkelvin airstain21-Aug-07 18:25 
GeneralI also met about the CArray's bug! Pin
taianmonkey4-Jan-07 20:54
membertaianmonkey4-Jan-07 20:54 
GeneralRe: I also met about the CArray's bug! Pin
Warren Stevens5-Jan-07 4:59
memberWarren Stevens5-Jan-07 4:59 
Generalhi Warren Pin
bagchisandeep11-Jan-06 5:29
memberbagchisandeep11-Jan-06 5:29 
GeneralRe: hi Warren Pin
Warren D Stevens11-Jan-06 5:38
memberWarren D Stevens11-Jan-06 5:38 
GeneralPassing CAray object to a function Pin
bagchisandeep11-Jan-06 4:56
memberbagchisandeep11-Jan-06 4:56 
GeneralRe: Passing CAray object to a function Pin
Warren D Stevens11-Jan-06 5:06
memberWarren D Stevens11-Jan-06 5:06 
NewsUse std::vector instead Pin
Warren D Stevens8-Oct-05 5:21
memberWarren D Stevens8-Oct-05 5:21 
GeneralCorrecting the class Pin
El Perro Azul7-Oct-05 12:52
memberEl Perro Azul7-Oct-05 12:52 
AnswerRe: Correcting the class Pin
Warren D Stevens8-Oct-05 5:01
memberWarren D Stevens8-Oct-05 5:01 
GeneralPassing &amp; Returning CArray Object with function Pin
Renugopal19-Jun-05 21:07
memberRenugopal19-Jun-05 21:07 
GeneralRe: Passing &amp; Returning CArray Object with function Pin
Warren Stevens15-Aug-05 8:32
memberWarren Stevens15-Aug-05 8:32 
GeneralUsing CArray &lt;CRgn, CRgn&gt; Pin
Rajesh_Parameswaran3-Dec-04 23:12
memberRajesh_Parameswaran3-Dec-04 23:12 
GeneralRe: Using CArray &lt;CRgn, CRgn&gt; Pin
Warren Stevens8-Dec-04 17:29
memberWarren Stevens8-Dec-04 17:29 
GeneralRe: Using CArray &lt;CRgn, CRgn&gt; Pin
Warren Stevens9-Dec-04 3:40
memberWarren Stevens9-Dec-04 3:40 
QuestionHow big is the size in CArray? Pin
Anonymous3-Dec-04 20:51
sussAnonymous3-Dec-04 20:51 
AnswerRe: How big is the size in CArray? Pin
Warren Stevens8-Dec-04 17:22
memberWarren Stevens8-Dec-04 17:22 
QuestionCArray problem?? Pin
owais31-Jul-03 20:06
memberowais31-Jul-03 20:06 
AnswerRe: CArray problem?? Pin
Warren D Stevens5-Aug-03 16:16
memberWarren D Stevens5-Aug-03 16:16 
GeneralAnd CArray not be nested... Pin
sclzmbie16-Apr-03 16:28
membersclzmbie16-Apr-03 16:28 
GeneralRe: And CArray not be nested... Pin
sclzmbie16-Apr-03 16:29
membersclzmbie16-Apr-03 16:29 
GeneralRe: And CArray not be nested... Pin
Warren D Stevens18-Apr-03 7:31
memberWarren D Stevens18-Apr-03 7:31 
GeneralNew elements Pin
Madmaximus6-Jun-02 8:05
memberMadmaximus6-Jun-02 8:05 
GeneralRe: New elements Pin
Warren Stevens18-Jul-02 11:10
memberWarren Stevens18-Jul-02 11:10 
GeneralThere's more to this Pin
Petr Novotny2-Oct-00 21:27
sussPetr Novotny2-Oct-00 21:27 
Generalmemcpy! Pin
Wilka30-Sep-00 17:15
sussWilka30-Sep-00 17:15 
GeneralI knew this all along Pin
Rodger Bernstein29-Sep-00 12:32
sussRodger Bernstein29-Sep-00 12:32 
GeneralRe: I knew this all along Pin
张自豪17-Mar-03 18:17
suss张自豪17-Mar-03 18:17 
GeneralAnother option: use std::vector Pin
Paul McKenzie28-Sep-00 9:15
sussPaul McKenzie28-Sep-00 9:15 
GeneralRe: Another option: use std::vector Pin
John Bates3-Oct-00 15:09
sussJohn Bates3-Oct-00 15:09 
GeneralRe: Another option: use std::vector Pin
Jonathan Gilligan3-Oct-00 21:48
sussJonathan Gilligan3-Oct-00 21:48 
GeneralRe: Another option: use std::vector Pin
Norbert Muench3-Oct-00 22:39
sussNorbert Muench3-Oct-00 22:39 
GeneralRe: Another option: use std::vector Pin
Martin Richter3-Oct-00 22:36
sussMartin Richter3-Oct-00 22:36 

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 | Terms of Use | Mobile
Web02 | 2.8.150728.1 | Last Updated 28 Sep 2000
Article Copyright 2000 by Warren Stevens
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid