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

Jump to bottom

Kdtree is built too early in savegame loading process #7371

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

Kdtree is built too early in savegame loading process #7371

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

Comments

@PeterN
Copy link
Member

PeterN commented Mar 13, 2019 •
edited

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
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Member Author

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
Copy link
Member Author

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
Copy link
Member Author

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
Copy link
Contributor

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
Fix OpenTTD#7371: Avoid dependency on foundations of town tile during…
f5f356c 
… saveload
nielsmh added a commit to nielsmh/OpenTTD that referenced this issue Mar 23, 2019
@nielsmh
Fix OpenTTD#7371: Avoid dependency on foundations of town tile during…
ca94ede 
… saveload
@JGRennison
Copy link
Contributor

JGRennison commented Apr 1, 2019 •
edited

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
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor

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
@nielsmh
Fix OpenTTD#7371: Avoid dependency on foundations of town tile during…
97e92ff 
… saveload
@LordAro
Copy link
Member

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

nielsmh added a commit to nielsmh/OpenTTD that referenced this issue May 2, 2019
@nielsmh
Fix OpenTTD#7371: Avoid dependency on foundations of town tile during…
54b76d4 
… saveload
nielsmh added a commit to nielsmh/OpenTTD that referenced this issue May 11, 2019
@nielsmh
Fix OpenTTD#7371: Avoid dependency on foundations of town tile during…
565ff91 
… saveload
@nielsmh nielsmh mentioned this issue Dec 1, 2019
Merged
douiwby pushed a commit to douiwby/OpenTTD that referenced this issue Apr 16, 2020
@nielsmh @douiwby
Fix OpenTTD#7371: Avoid dependency on foundations of town tile during…
832a595 
… saveload
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@nielsmh nielsmh

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@PeterN @nielsmh @JGRennison @LordAro