Pointer Invalidation issues

[olduser]

CLLNode<IDInfo>* pUnitNode = pPlot->headUnitNode();

                    while (pUnitNode != NULL)
                    {
                        CvUnit* pLoopUnit = ::getUnit(pUnitNode->m_data);
                        pUnitNode = pPlot->nextUnitNode(pUnitNode);

                        if (pLoopUnit->getTeam() == getTeam())
                        {
                            Code that modifies the list of units on a PLOT!
                        }
                    }

CivIV and C2C have issues with pointer invalidation, this happens in code like the above segment.

Every time the list of units on a plot or in a selectiongroup is modified after calling nextUnitNode it's possible that the pUnitNode pointer becomes invalid. This is a programming error that is becomming a problem especially with Windows 10 because newer windows versions have more agressive memory management.

C2C already has all kinds of code to avoid crashes because of this issues but most of them are flawed i post some examples later.

 

[raxo2222]

I wonder if this is cause of crashes, that happen on Windows 10 but not on Windows 7.

 

[olduser]

Here a example from a another mod a few years ago.

I used the save from http://forums.civfanatics.com/showpost.php?p=14247568&postcount=670 in my tests. A AI stacks with 5 units attacks a city the first two kill the defenders and the third takes the city and the game crashes.
To see what's going on create an conditional Breakpoint in the pLoopUnit->move(pPlot, true); line.

This is where the unit moves and takes the city.


The owner of the plot changes and the CvSelectionGroup the game is currently processing is modified. It seems that Windows10 handles memory differently and the way this game mechanism is programmed no longer works. I don't know your mod as well as you do but there must be a way to avoid this.

This is the Callstack unitil the memory from the pUnitNode is released.

>    CvGameCoreDLL.dll!operator delete(void * p) Line 25    C++
     [External Code]   
     CvGameCoreDLL.dll!CLinkList<IDInfo>::deleteNode(CLLNode<IDInfo> * pNode) Line 265    C++
     CvGameCoreDLL.dll!CvSelectionGroup::deleteUnitNode(CLLNode<IDInfo> * pNode) Line 4241    C++
     CvGameCoreDLL.dll!CvSelectionGroup::removeUnit(CvUnit * pUnit) Line 4209    C++
     CvGameCoreDLL.dll!CvUnit::joinGroup(CvSelectionGroup * pSelectionGroup, bool bRemoveSelected, bool bRejoin) Line 9204    C++
     CvGameCoreDLL.dll!CvUnit::setXY(int iX, int iY, bool bGroup, bool bUpdate, bool bShow, bool bCheckPlotVisible) Line 9354    C++
     CvGameCoreDLL.dll!CvUnit::jumpToNearestValidPlot() Line 2978    C++
     CvGameCoreDLL.dll!CvPlot::verifyUnitValidPlot() Line 927    C++
     CvGameCoreDLL.dll!CvPlot::setOwner(PlayerTypes eNewValue, bool bCheckUnits, bool bUpdatePlotGroup) Line 5322    C++
     CvGameCoreDLL.dll!CvPlot::updateCulture(bool bBumpUnits, bool bUpdatePlotGroups) Line 604    C++
     CvGameCoreDLL.dll!CvPlot::changeCultureRangeCities(PlayerTypes eOwnerIndex, int iRangeIndex, int iChange, bool bUpdatePlotGroups) Line 8956    C++
     CvGameCoreDLL.dll!CvCity::setCultureLevel(CultureLevelTypes eNewValue, bool bUpdatePlotGroups) Line 7753    C++
     CvGameCoreDLL.dll!CvCity::kill(bool bUpdatePlotGroups) Line 777    C++
     CvGameCoreDLL.dll!CvPlayer::acquireCity(CvCity * pOldCity, bool bConquest, bool bTrade, bool bUpdatePlotGroups) Line 1628    C++
     CvGameCoreDLL.dll!CvUnit::setXY(int iX, int iY, bool bGroup, bool bUpdate, bool bShow, bool bCheckPlotVisible) Line 9584    C++
     CvGameCoreDLL.dll!CvUnit::move(CvPlot * pPlot, bool bShow) Line 2862    C++
     CvGameCoreDLL.dll!CvSelectionGroup::groupMove(CvPlot * pPlot, bool bCombat, CvUnit * pCombatUnit, bool bEndMove) Line 3411    C++
     CvGameCoreDLL.dll!CvUnit::updateCombat(bool bQuick) Line 1564    C++
     CvGameCoreDLL.dll!CvUnit::attack(CvPlot * pPlot, bool bQuick) Line 2717    C++
     CvGameCoreDLL.dll!CvSelectionGroup::groupAttack(int iX, int iY, int iFlags, bool & bFailedAlreadyFighting) Line 3360    C++
     CvGameCoreDLL.dll!CvSelectionGroupAI::AI_update() Line 212    C++
     CvGameCoreDLL.dll!CvPlayerAI::AI_unitUpdate() Line 1336    C++
     CvGameCoreDLL.dll!CvGame::updateMoves() Line 6925    C++
     CvGameCoreDLL.dll!CvGame::update() Line 2172    C++
     Civ4BeyondSword.exe!00415321()    Unknown
     [Frames below may be incorrect and/or missing, no symbols loaded for Civ4BeyondSword.exe]   
     Civ4BeyondSword.exe!00686bc8()    Unknown
     Civ4BeyondSword.exe!004d6f46()    Unknown
     Civ4BeyondSword.exe!008f497f()    Unknown
     [External Code]

 

[olduser]

The real bug is removing units from a selection group while iterating through those units. The IDInfo struct at the adress the pLoopUnitNode is pointing to is removed because a unit is removed from the group. Later a XYCords struct is allocated using new at that address and the pLoopUnitNode is now pointing to that struct. This can't work and is just poorly programmed.

I'am just not sure how to really fix this without creating other issues.

 

[Anq]

In this case, I think one should call pPlot->removeUnit(pLoopUnit) before the kill to prevent pointer invalidation, is this correct?
So the general pattern here is they are dealing with doubly linked lists. Deleting a pointer whilst traversing a list creates potential pointer invalidation, if one tries to jump back to a previous node.

Pointer access violation happens as soon as the list is being deleted. This is because you cannot delete a pointer twice.

https://forums.civfanatics.com/thre...f-february-2018.629241/page-196#post-15493621
This earlier bug report shows the program crashed at ~CvTalkingHeadMessage()

 

[olduser]

Deleting a pointer whilst traversing a list creates potential pointer invalidation, if one tries to jump back to a previous node.

Going to the next node in a loop is not possible if the next node has been changed or removed.

 

[Anq]

Going to the next node in a loop is not possible if the current or next node has been changed or removed.

Although m_data is deleted, the m_prev and m_next pointers still point to the other nodes, so I think the while loop may continue, but the game will crash at the destruction of the list.
Some time? I haven't study that code fully.

 

[olduser]

Although m_data is deleted

Yes and in the current coding the IDInfo m_data is being read after it's been removed and the memory has possibly been overwritten with other data at that time it is being read.

the m_prev and m_next pointers still point to the other nodes

That information is invalid as soon as the node has been deleted.

 

[olduser]

The other issue is that C2C has lot's of flawed code to move around this issue in various places.
Here a example

            std::set<int> movedUnitIds;

            while (true)
            {
                pUnitNode = pOldPlot->headUnitNode();
                pLoopUnit = NULL;

                while (pUnitNode != NULL)
                {
                    if (movedUnitIds.empty() || movedUnitIds.find(pUnitNode->m_data.iID) == movedUnitIds.end())
                    {
                        pLoopUnit = ::getUnit(pUnitNode->m_data);

                        FAssertMsg(pLoopUnit != NULL, "NULL unit reached in the selection group");

                        if (pLoopUnit != NULL)
                            break;
                    }

                    pUnitNode = pOldPlot->nextUnitNode(pUnitNode);
                }

                if (pLoopUnit == NULL)
                    break;
               
                movedUnitIds.insert(pLoopUnit->getID());

                if (pLoopUnit->getTransportUnit() == this)
                {
                    //GC.getGameINLINE().logOOSSpecial(22, pLoopUnit->getID(), iX, iY);
                    pLoopUnit->setXY(iX, iY, bGroup, false);
                }
            }

This is wrong because only the unit ID's are stored in a std::set and units of different players can have the same ID. The complete IDInfo must be used here.
It's also inefficient because of std::set is used.

I think something like this could work much better but i'am not yet sure if it's a proper solution.

            pUnitNode = pOldPlot->headUnitNode();
            std::vector<IDInfo> cargoUnits;
            while (pUnitNode != NULL)
            {
                pLoopUnit = ::getUnit(pUnitNode->m_data);
                pUnitNode = pOldPlot->nextUnitNode(pUnitNode);

                if (pLoopUnit->getTransportUnit() == this)
                {
                    //GC.getGameINLINE().logOOSSpecial(22, pLoopUnit->getID(), iX, iY);
                    cargoUnits.push_back(pLoopUnit->getIDInfo());
                }
            }
            for(std::vector<IDInfo>::const_iterator it = cargoUnits.begin(), end = cargoUnits.end(); it != end; ++it)
            {
                pLoopUnit = ::getUnit(*it);
                if (pLoopUnit != NULL)
                {
                    pLoopUnit->setXY(iX, iY, bGroup, false);
                }
            }

 

[Thunderbrd]

It's also inefficient because of std::set is used.

If I'm not mistaken, this was the problem that I was copying the layout of some coding to try to resolve that was causing the std::find on a set inefficiency. I'm just now hearing about and starting to really learn what a set is beyond just seeing code and having a clue how to work with it based on my understanding of vectors. Only in the last month did I really even come to grasp that there WAS such a thing as a set, as distinct from a vector, array, or map, thanks to these discussions that this bug brought up. I have a lot to learn here... all the more than I thought.

 

[olduser]

If I'm not mistaken, this was the problem that I was copying the layout of some coding to try to resolve that was causing the std::find on a set inefficiency

That's another problem.

std::set is a ordered Container every time you insert something it must search the location where the new item must be located to keep that order. This takes time and std::set should only be used if it's necessary to have a collection ordered otherwise a std::vector could be used instead.

 

[olduser]

The other issue is that C2C has lot's of flawed code to move around this issue in various places.
Here a example

            std::set<int> movedUnitIds;

            while (true)
            {
                pUnitNode = pOldPlot->headUnitNode();
                pLoopUnit = NULL;

                while (pUnitNode != NULL)
                {
                    if (movedUnitIds.empty() || movedUnitIds.find(pUnitNode->m_data.iID) == movedUnitIds.end())
                    {
                        pLoopUnit = ::getUnit(pUnitNode->m_data);

                        FAssertMsg(pLoopUnit != NULL, "NULL unit reached in the selection group");

                        if (pLoopUnit != NULL)
                            break;
                    }

                    pUnitNode = pOldPlot->nextUnitNode(pUnitNode);
                }

                if (pLoopUnit == NULL)
                    break;
              
                movedUnitIds.insert(pLoopUnit->getID());

                if (pLoopUnit->getTransportUnit() == this)
                {
                    //GC.getGameINLINE().logOOSSpecial(22, pLoopUnit->getID(), iX, iY);
                    pLoopUnit->setXY(iX, iY, bGroup, false);
                }
            }

This is wrong because only the unit ID's are stored in a std::set and units of different players can have the same ID. The complete IDInfo must be used here.
It's also inefficient because of std::set is used.

I think something like this could work much better but i'am not yet sure if it's a proper solution.

            pUnitNode = pOldPlot->headUnitNode();
            std::vector<IDInfo> cargoUnits;
            while (pUnitNode != NULL)
            {
                pLoopUnit = ::getUnit(pUnitNode->m_data);
                pUnitNode = pOldPlot->nextUnitNode(pUnitNode);

                if (pLoopUnit->getTransportUnit() == this)
                {
                    //GC.getGameINLINE().logOOSSpecial(22, pLoopUnit->getID(), iX, iY);
                    cargoUnits.push_back(pLoopUnit->getIDInfo());
                }
            }
            for(std::vector<IDInfo>::const_iterator it = cargoUnits.begin(), end = cargoUnits.end(); it != end; ++it)
            {
                pLoopUnit = ::getUnit(*it);
                if (pLoopUnit != NULL)
                {
                    pLoopUnit->setXY(iX, iY, bGroup, false);
                }
            }

@Thunderbrd

At least this change should be made before the release the rest could be looked at later.

 

[Thunderbrd]

@Thunderbrd

At least this change should be made before the release the rest could be looked at later.

We'll have to address this after release.

You said:

The other issue is that C2C has lot's of flawed code to move around this issue in various places.
Here a example

Which tells me there's a lot of these spots to look at and not all of them have been identified here, and:

This is wrong because only the unit ID's are stored in a std::set and units of different players can have the same ID. The complete IDInfo must be used here.
It's also inefficient because of std::set is used.

From which, I gather, crashes are infrequent, though can happen, and we're talking about an efficiency issue (not exactly 100% critical since we can always improve efficiency in many ways)
and most importantly:

I think something like this could work much better but i'am not yet sure if it's a proper solution.

If you aren't dead sure it's the right way to go with the fix, I don't want to insert something untested into the code anywhere that could cause some kind of unexpected issues worse than what we have now. I'm not saying this is not a high priority matter - I totally get it because you and I have been encountering these problems for a long time and they are confounding as hell. I'm saying I'd prefer to go with the devil as we know it for the release than the one we don't yet know, applied in only one of many potential places it should be. We can always find very good reason to hold up releases. Hopefully we can get these fixes implemented soon after release and they work great and become a big part of why we'll have a good v40 release and for those who encounter the problem we can simply say, yeah we dealt with that already so get the latest revision and start a new game and go from there. We run into these bugs now and then but not at such frequency that its worthwhile to introduce an untested element just before release. I believe you're right that it's a good fix but man... if for any reason it isn't and we only find out from feedback after we release this thing, that'd be a nightmare.

 

[billw2015]

Necroing this as I just added something relevant:
https://github.com/caveman2cosmos/C...cfd34d225534decd0df/Sources/idinfo_iterator.h

An implementation here:
https://github.com/caveman2cosmos/C...2f067d874cd9f878eb5d8d7/Sources/CvPlot.h#L823

Example of usage here:
https://github.com/caveman2cosmos/C...874cd9f878eb5d8d7/Sources/CvCityAI.cpp#L10056
(you can see many more in that file).
As well as making the code a lot clearer and neater, it also encapsulates the behavior of iterating over the linked lists into a single place. This will make implementing more robust behavior easier hopefully.