Source Code Project Mantis - FSSCP
View Issue Details
0002165FSSCPgraphicspublic2010-03-27 07:562012-12-17 04:05
Reporteravaman 
Assigned ToGoober5000 
PrioritynormalSeveritycrashReproducibilityrandom
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version3.6.12 RC1 
Target VersionFixed in Version 
Summary0002165: Vector iterator becomes invalid in Particle.cpp
DescriptionIn function particle_move_all() the vector iterator "p" inside a loop becomes
invalid after manipulation of the vector itself.
Tested with "The babylon project".

My fixed version attached.
TagsNo tags attached.
Attached Filestxt particle_move_all.txt (1,271) 2010-03-27 07:56
http://scp.indiegames.us/mantis/file_download.php?file_id=1461&type=bug
diff fix_2165.diff (624) 2010-03-29 08:05
http://scp.indiegames.us/mantis/file_download.php?file_id=1465&type=bug
patch particle.cpp.patch (2,442) 2012-12-03 13:08
http://scp.indiegames.us/mantis/file_download.php?file_id=2010&type=bug

Notes
(0011837)
The_E   
2010-03-27 14:08   
It's easier if you provide .patch files a generated by your svn application rather than text files like that.
(0011840)
avaman   
2010-03-28 11:52   
I've used SVN very rarely. Thanks for the info. Now I know what these patches mean.
(0011842)
Genghis   
2010-03-29 08:06   
I've attached a patch file which represents the same fix, called "fix_2165.diff".

(0011846)
portej05   
2010-03-31 07:09   
I put a fix in for that back when I overhauled the particle code to use a free-queue (that was optimisation round 1), but it appears to have been reverted.
Additionally, I remember seeing in some GameDev presentations that using .size could represent a small performance hit, especially in loops - better to stick with iterators and reload them when they're invalidated.
(0013418)
Echelon9   
2012-03-18 10:12   
I think I've seen this issue in Diaspora -- looking into the patch
(0013432)
Echelon9   
2012-04-01 09:22   
This patch throws compilation errors with Clang on latest trunk r8642.
It will have to be rewritten, as it doesn't look like it is based off an unmodified trunk codebase?

(0014275)
Valathil   
2012-12-03 12:29   
(Last edited: 2012-12-03 13:08)
Not only that but this whole code is completely wrong. You cant remove arbitrary entries from a std::vector without causing a realloc. What seems to be required here is a change to a linked list.

EDIT: Attached a patch that should work

(0014364)
niffiwan   
2012-12-08 19:29   
I've got a question on the use of a linked list - how many elements are we expecting the list to contain? I've seen in other areas of the code (r9128) that large lists (maybe 50k-100k+ entries) perform *extremely* slowly when you need to iterate over every entry in the list. I think it's something to do with data locality & caches.

Of course, if the number of expected list entries is small, it really doesn't matter (see premature optimisation ;).
(0014366)
Echelon9   
2012-12-08 20:07   
Valathil your linked list patch looks fine.
(0014370)
Zacam   
2012-12-08 22:00   
Fix committed to trunk@9411.
(0014400)
Goober5000   
2012-12-09 22:47   
Putting this to code review because I'd like to see an answer to niffiwan's question as well. >.>

Also, I would like to know whether the order of particles in the vector is significant. If the order doesn't matter, then an easy way to delete items from the middle of the vector is to swap the nth element with the last element, then decrease the size by 1.
(0014411)
Valathil   
2012-12-10 14:27   
That exact thing was done before the fix. Normally pop_back shouldn't cause an iterator invalidation and i checked the original code and can't see how this even happened in the first place. List size is dependent on how much particles are active but i think in even the biggest battle situations it wont get over 10k. So we either can make it a vector again and risk the corruption again that should'nt happen in the first place or just leave the linked list that works as it should.
(0014414)
niffiwan   
2012-12-10 16:08   
10k entries is probably fine, I think that's about the size of other list I was referring to when it was working OK (i.e. before the changes that caused it to grow larger)
(0014417)
Goober5000   
2012-12-10 20:14   
Personally, I would put it back to vector and take a closer look at why the iterator became invalid. You never know, an additional pair of eyes may be able to help spot the problem.
(0014418)
Valathil   
2012-12-10 20:47   
whatever do what you want not gonna stop you
(0014419)
Goober5000   
2012-12-10 21:07   
Is there a test mission that will reliably duplicate the invalidation?
(0014422)
The_E   
2012-12-11 01:48   
>Personally, I would put it back to vector and take a closer look at why the iterator became invalid. You never know, an additional pair of eyes may be able to help spot the problem.

You do know that any manipulation of a vectors' size will invalidate all iterators for that vector, yes?
(0014423)
Goober5000   
2012-12-11 01:51   
According to my research, the only iterators that are invalidated are those positioned after the deleted items. If the deleted items are at the end of the vector, then there shouldn't be a problem.
(0014424)
Valathil   
2012-12-11 02:53   
not pop_back google it
(0014425)
Goober5000   
2012-12-11 11:34   
I did:
http://stackoverflow.com/questions/62340/does-pop-back-really-invalidate-all-iterators-on-an-stdvector
"The call to pop_back() removes the last element in the vector and so the iterator to that element is invalidated. The pop_back() call does not invalidate iterators to items before the last element, only reallocation will do that."

Anyway, I have further information from Taylor. Stay tuned for an update.
(0014502)
Goober5000   
2012-12-17 04:05   
Okay, the issue is that pop_back will invalidate the iterator pointing to the very last particle in the vector. This means that when that particle is removed, the iterator points to nothing rather than pointing to Particles.end() as would be expected.

Fixed in r9446. I've also restored the use of SCP_vector because this is far more efficient than SCP_list.

Issue History
2010-03-27 07:56avamanNew Issue
2010-03-27 07:56avamanFile Added: particle_move_all.txt
2010-03-27 14:08The_ENote Added: 0011837
2010-03-28 11:52avamanNote Added: 0011840
2010-03-29 08:05GenghisFile Added: fix_2165.diff
2010-03-29 08:06GenghisNote Added: 0011842
2010-03-29 08:06GenghisNote Edited: 0011842
2010-03-29 08:13GenghisStatusnew => assigned
2010-03-29 08:13GenghisAssigned To => Genghis
2010-03-31 07:09portej05Note Added: 0011846
2012-03-06 08:06Echelon9Statusassigned => code review
2012-03-18 10:12Echelon9Note Added: 0013418
2012-04-01 09:22Echelon9Note Added: 0013432
2012-04-01 09:22Echelon9Note Edited: 0013432bug_revision_view_page.php?bugnote_id=13432#r107
2012-12-03 12:29ValathilNote Added: 0014275
2012-12-03 13:08ValathilFile Added: particle.cpp.patch
2012-12-03 13:08ValathilNote Edited: 0014275bug_revision_view_page.php?bugnote_id=14275#r274
2012-12-08 19:29niffiwanNote Added: 0014364
2012-12-08 20:07Echelon9Note Added: 0014366
2012-12-08 22:00ZacamChangeset attached => fs2open trunk r9411
2012-12-08 22:00ZacamNote Added: 0014370
2012-12-08 22:00ZacamStatuscode review => resolved
2012-12-08 22:00ZacamResolutionopen => fixed
2012-12-09 22:47Goober5000Note Added: 0014400
2012-12-09 22:47Goober5000Assigned ToGenghis => Valathil
2012-12-09 22:47Goober5000Statusresolved => code review
2012-12-09 22:47Goober5000Resolutionfixed => reopened
2012-12-10 14:27ValathilNote Added: 0014411
2012-12-10 16:08niffiwanNote Added: 0014414
2012-12-10 20:14Goober5000Note Added: 0014417
2012-12-10 20:47ValathilNote Added: 0014418
2012-12-10 21:07Goober5000Note Added: 0014419
2012-12-11 01:48The_ENote Added: 0014422
2012-12-11 01:51Goober5000Note Added: 0014423
2012-12-11 02:53ValathilNote Added: 0014424
2012-12-11 11:34Goober5000Note Added: 0014425
2012-12-11 11:34Goober5000Assigned ToValathil => Goober5000
2012-12-11 11:34Goober5000Statuscode review => assigned
2012-12-17 03:28Goober5000Changeset attached => fs2open trunk r9445
2012-12-17 04:04Goober5000Changeset attached => fs2open trunk r9446
2012-12-17 04:05Goober5000Note Added: 0014502
2012-12-17 04:05Goober5000Statusassigned => resolved
2012-12-17 04:05Goober5000Resolutionreopened => fixed