Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#11494 closed defect (invalid)

BASE: Possible use of invalid iterators

Reported by: Tkachov Owned by: criezy
Priority: high Component: --Unset--
Version: Keywords: iterators, invalidate, erase
Cc: Game:

Description

I've stumbled onto C++ iterators-related comment (in Russian: https://habr.com/ru/post/492410/#comment_21566838): someone cached collection.end() and then used i = collection.erase(i), which invalidates old iterators.

So I've decided to look through ScummVM code and I've found some places I think might use invalid iterators. I've used GitHub search and briefly read the files, so I might've skipped something or made a false positive mistake. Also, I'm not sure if ScummVM iterators invalidate after erase() or not.

Anyways, here are these places:

https://github.com/scummvm/scummvm/blob/30c00656e1d6e6e8420c662755527ac3b08ee8ff/backends/timer/default/default-timer.cpp#L187L189

	for (TimerSlotMap::iterator i = _callbacks.begin(), end = _callbacks.end(); i != end; ++i) {
		if (i->_value == callback)
			_callbacks.erase(i);
  1. _callbacks.end() is cached, but erase() is used.
  2. erase() returns new valid iterator, but this code continues to use the old one.

https://github.com/scummvm/scummvm/blob/46ba0500cebf4ed6334d43b6b48b2079f06d05d0/engines/ultima/ultima8/gumps/gump.cpp#L63L67

	Std::list<Gump *>::iterator end = _children.end();

	while (it != end) {
		Gump *g = *it;
		it = _children.erase(it);

erase() probably invalidates that cached end. Comment up there says "Delete all children", so I don't see why erase() is even needed. One could iterate through all the children, deleting each of them and then use clear(). Or, maybe, do something like this:

while (!ch.empty()) {
	delete *ch.begin();
	ch.erase(ch.begin());
}

https://github.com/scummvm/scummvm/blob/1a097b1d971e6e3cf3c10f6eb7c7a30def2d2f7c/engines/cruise/gfxModule.cpp#L252L265
and the same code at
https://github.com/scummvm/scummvm/blob/1a097b1d971e6e3cf3c10f6eb7c7a30def2d2f7c/engines/tony/gfxcore.cpp#L398L412

	for (rOuter = _dirtyRects.begin(); rOuter != _dirtyRects.end(); ++rOuter) {
		rInner = rOuter;
		while (++rInner != _dirtyRects.end()) {
				...
				// remove the inner rect from the list
				_dirtyRects.erase(rInner);

				// move back to beginning of list
				rInner = rOuter;

I see why this probably works: erase() only invalidates iterators pointing to elements further than the erased one, so earlier iterators are fine. If that's not so, rOuter should be as invalid as rInner, and code probably should be rewritten to use integer indexes instead.


https://github.com/scummvm/scummvm/blob/6ed8dea8297480d4c42ed0d38a23734df48067e6/engines/zvision/graphics/render_manager.cpp#L743

_subsList.erase(it);

The cycle goes on without break or return there, so erase() return value should be used to update it and it++ should not be called.


https://github.com/scummvm/scummvm/blob/e3abab45ab27349a6296a5c3c447d331f3e5167b/engines/gob/inter.h#L61

#define CLEAROPCODEGOB(i)  _opcodesGob.erase(i)

I couldn't find usages of CLEAROPCODEGOB, so I don't know if that is even related to iterators, but if it is, its return value should be used and end() around there should not be cached.

Change History (4)

comment:1 by raziel-, 4 years ago

Summary: Possible usage of invalid iteratorsBASE: Possible use of invalid iterators

comment:2 by sev-, 4 years ago

Priority: lowhigh

comment:3 by criezy, 4 years ago

Owner: set to criezy
Resolution: fixed
Status: newclosed

Thank you for the reports.
The good news is that they are all false positive.


DefaultTimerManager: This is a false positive as _callbacks is a Common::HashMap and calling HashMap::erase(iterator) does not invalidate iterators. Even iterators on the erased node remain partially valid. They can no longer be dereferenced, but can still be used for the iteration. Also erase() does not actually return anything.


Ultima8: This is also a false positive. This time the code is using a Std::list that derives from Common::List. Common::List is implemented as a linked list, and erase only invalidates iterators pointing to the erased item.


Cruise and Tony: Again false positives. They are using a Common::List<Common::Rect> (so again only iterators to the erased items are invalidated).


ZVision: _subsList is a SubtitleMap which is a typedef tp a Common::HashMap. So the code is actually correct (HashMap::erase() does not return an iterator, and we can continue iterating using the current one).


Gob: _opcodesGob is a Common::HashMap. So erase() does not return anything and does not invalidate iterators.

comment:4 by criezy, 4 years ago

Resolution: fixedinvalid
Note: See TracTickets for help on using tickets.