Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Kdtree is built too early in savegame loading process #7371

Closed
PeterN opened this issue Mar 13, 2019 · 12 comments
Assignees

Comments

@PeterN
Copy link
Member

@PeterN PeterN commented Mar 13, 2019

Version of OpenTTD

20190312-master-gdea7f078f4

Expected result

Old savegame is loaded the same as before implementation of k-d trees.

Actual result

Assertion failure on loading old savegame during building of k-d tree structures.

openttd: src/core/pool_type.hpp:113: Titem *Pool<Object, unsigned int, 64, 16711680, PoolType::PT_NORMAL, false, true>::Get(size_t) [Titem = Object, Tindex = unsigned int, Tgrowth_step = 64, Tmax_size = 16711680, Tpool_type = PoolType::PT_NORMAL, Tcache = false, Tzero = true]: Assertion index < this->first_unused' failed.`

Steps to reproduce

Download "Public Server Game 201 Final" from https://wiki.openttdcoop.org/PublicServer:Archive_-_Games_201_-_210#gameid_201
Load save game

Crash occurs because building k-d tree structure accesses map array before map array has been updated. In this particular case it is because the accessing the map array before SLV_186 conversion results in invalid object index, however there are likely more causes.

Before savegame data is converted, normal game accessors should not be used, but k-d tree uses these to build its structures. These lines are unsafe in their current position:

    RebuildTownKdtree();
    RebuildStationKdtree();
    /* This needs to be done even before conversion, because some conversions will destroy objects
     * that otherwise won't exist in the tree. */
    RebuildViewportKdtree();
@nielsmh

This comment has been minimized.

Copy link
Contributor

@nielsmh nielsmh commented Mar 13, 2019

I originally tried building the trees late in the loading, but that ended up crashing for different reasons, when converting a very old save (the master title screen).

@nielsmh

This comment has been minimized.

Copy link
Contributor

@nielsmh nielsmh commented Mar 13, 2019

I'm not sure I see why SLV_186 should be relevant, it only seems to concern map objects, not towns, stations, or signs.

@PeterN

This comment has been minimized.

Copy link
Member Author

@PeterN PeterN commented Mar 13, 2019

Town signs can be on a tile that has been replaced with an object. During the test for sign position, it queries the tile to get foundation status, and that depends on the object information, which depends on the object ID, which SLV_186 shuffles about. This is just one particular case, of course. Town signs could be on other tile types of course.

@PeterN

This comment has been minimized.

Copy link
Member Author

@PeterN PeterN commented Mar 13, 2019

I was able to get this savegame to load by deferring k-d tree generation til the end of AfterLoadGame, with a simple guard to make sure no k-d tree functions were called whilst still within AfterLoadGame. I had to make CalcClosestTown... fallback to the original method for this.

@PeterN

This comment has been minimized.

Copy link
Member Author

@PeterN PeterN commented Mar 14, 2019

Here's my branch with the test code in place. This is obviously not production ready! https://github.com/PeterN/OpenTTD/commits/fix-7371

@nielsmh nielsmh self-assigned this Mar 23, 2019
@nielsmh

This comment has been minimized.

Copy link
Contributor

@nielsmh nielsmh commented Mar 23, 2019

The absolutely simplest fix is changing the sign location calculation so it does not depend on foundations status at all. It might make some town signs sit in a "wrong" location, but would that really be a problem?

nielsmh added a commit to nielsmh/OpenTTD that referenced this issue Mar 23, 2019
nielsmh added a commit to nielsmh/OpenTTD that referenced this issue Mar 23, 2019
@JGRennison

This comment has been minimized.

Copy link
Contributor

@JGRennison JGRennison commented Apr 1, 2019

Leaving RebuildTownKdtree and RebuildStationKdtree at the start, and moving RebuildViewportKdtree to the end, is sufficient to resolve the issue (for this particular save game at least).

_viewport_sign_kdtree is not read during AfterLoadGame, and therefore does not need to be initialised before conversion.
_town_kdtree is required for CalcClosestTown and such during conversion, but this does not inspect tile contents, foundations, etc.

@nielsmh

This comment has been minimized.

Copy link
Contributor

@nielsmh nielsmh commented Apr 1, 2019

I think there were some situations where stations and/or waypoints are created or removed during conversion, which will trigger an update of the viewport sign tree, which will fail if it wasn't built beforehand.

@JGRennison

This comment has been minimized.

Copy link
Contributor

@JGRennison JGRennison commented Apr 1, 2019

Removing a non-existent key from an empty kd tree isn't an error, likewise adding a key to the kd tree before it is otherwise filled is also harmless.

MoveWaypointsToBaseStations and MoveBuoysToWaypoints appear to be the functions in question. The former doesn't appear to use _viewport_sign_kdtree. The latter appears to perform harmless removals from _viewport_sign_kdtree. In both cases the kd tree isn't added to and so RebuildViewportKdtree should be called afterwards.

@nielsmh

This comment has been minimized.

Copy link
Contributor

@nielsmh nielsmh commented Apr 1, 2019

Right now, my k-d tree code considers it an error it attempt removing an element that does not exist, and will assert.

OpenTTD/src/core/kdtree.hpp

Lines 211 to 215 in 92d5835

/* Which side to remove from */
size_t next = (ec < nc) ? n.left : n.right;
assert(next != INVALID_NODE); // node must exist somewhere and must be found before a leaf is reached
/* Descend */
size_t new_branch = this->RemoveRecursive(element, next, level + 1);

This is under the assumption that it's an error in the upper layer if the tree is not correctly maintained.

@JGRennison

This comment has been minimized.

Copy link
Contributor

@JGRennison JGRennison commented Apr 1, 2019

Asserting on removing a non-existing key is very surprising behaviour, and contradicts the documentation of the Remove method.

The savegame update code requires further changes if this is the intended behavour.

nielsmh added a commit to nielsmh/OpenTTD that referenced this issue Apr 1, 2019
@LordAro

This comment has been minimized.

Copy link
Member

@LordAro LordAro commented Apr 27, 2019

In the interests of reproducibility, I found the following 64x64 save that also crashes on load, and is fixed by #7398
pr7398.zip

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.