Skip to content

Make tile building reproducible#2480

Merged
merkispavel merged 9 commits intomasterfrom
consistent-tile-build
Jul 28, 2020
Merged

Make tile building reproducible#2480
merkispavel merged 9 commits intomasterfrom
consistent-tile-build

Conversation

@merkispavel
Copy link
Copy Markdown
Contributor

@merkispavel merkispavel commented Jul 21, 2020 •
edited
Loading

Issue

At the moment if you try to run valhalla_build_tiles a few times with the same input data(config, pbfs) you'll get different tilesets(tile hash sums are different). The PR fixes that behavior

Example of how to compare tilesets

cd ${PATH_TO_FIRST_TILESETS} && find . -type f -exec md5 {} + | sort -k 2 > ../first_hash.txt && cd -
cd ${PATH_TO_SECOND_TILESETS} && find . -type f -exec md5 {} + | sort -k 2 > ../second_hash.txt && cd -
diff first_hash.txt second_hash.txt # must be empty after this PR

Tasklist

  • Add tests
  • Add #fixes with the issue number that this PR addresses
  • Generally use squash merge to rebase and clean comments before merging
  • Update the changelog

Requirements / Relations

Link any requirements here. Other pull requests this PR is based on?

@danpaz
Copy link
Copy Markdown
Collaborator

danpaz commented Jul 21, 2020

Is this reproducible with a gurka test? If so it seems worth adding a simple test that builds tiles twice using the same input map and checking the resulting tiles are the same.

@merkispavel
Copy link
Copy Markdown
Contributor Author

merkispavel commented Jul 21, 2020 •
edited
Loading

Is this reproducible with a gurka test? If so it seems worth adding a simple test that builds tiles twice using the same input map and checking the resulting tiles are the same.

Totally agreed! Didn't want to assign reviewers until I add tests.
The only thing is: I thought about using some small real world pbf(small country/extracted region) rather than "non-realworld" . Not sure which one is better

@danpaz
Copy link
Copy Markdown
Collaborator

danpaz commented Jul 21, 2020

The only thing is: I thought about using some small real world pbf(small country/extracted region) rather than "non-realworld" . Not sure which one is better

IMO, if a minimal fake map reproduces the issue it will be a lot simpler to write and understand that test, and it will run a lot faster in CI.

@merkispavel merkispavel force-pushed the consistent-tile-build branch from 77a328e to a83b0ba Compare July 24, 2020 00:37
@merkispavel merkispavel force-pushed the consistent-tile-build branch from a83b0ba to 33f0dae Compare July 24, 2020 00:40
@merkispavel merkispavel requested a review from danpaz July 24, 2020 10:20
@merkispavel merkispavel self-assigned this Jul 24, 2020
@gknisely gknisely self-requested a review July 24, 2020 14:45
gknisely
gknisely previously approved these changes Jul 24, 2020
View reviewed changes
@merkispavel
Copy link
Copy Markdown
Contributor Author

merkispavel commented Jul 24, 2020 •
edited
Loading

Hm, tests pass on my machine but fails in CI. Seems there're another UB somewhere in the code..
I built and ran this test locally with UB sanitizer. 4 UB errors(3 unique?) were found. Need some time to figure out what UB-s are critical for this test/building tiles.
Makes sense to me not to merge this PR until that to avoid flaky tests in the master

[----------] 1 test from GraphTileBuilder
[ RUN      ] GraphTileBuilder.TestBuildIsReproducible
[          ] generating map PBF at test/data/gurka_reproduce_tile_build/1/map.pbf
[          ] building tiles in test/data/gurka_reproduce_tile_build/1
../valhalla/baldr/graphtileheader.h:166:12: runtime error: downcast of address 0x615000010200 which does not point to an object of type 'const midgard::PointLL' (aka 'const GeoPoint<float>')
0x615000010200: note: object has invalid vptr
 5f 00 00 36  82 5e 3f 00 00 00 00 00  00 00 00 00 00 00 00 00  33 2e 30 2e 39 00 00 00  00 00 00 00
              ^~~~~~~~~~~~~~~~~~~~~~~
              invalid vptr
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../valhalla/baldr/graphtileheader.h:166:12 in
../valhalla/baldr/nodeinfo.h:65:41: runtime error: member call on address 0x615000000800 which does not point to an object of type 'valhalla::midgard::GeoPoint<float>'
0x615000000800: note: object has invalid vptr
 7f 00 00 41  82 5e 3f 00 00 00 00 00  00 00 00 00 00 00 00 00  33 2e 30 2e 39 00 00 00  00 00 00 00
              ^~~~~~~~~~~~~~~~~~~~~~~
              invalid vptr
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../valhalla/baldr/nodeinfo.h:65:41 in
../valhalla/baldr/nodeinfo.h:66:41: runtime error: member call on address 0x615000000800 which does not point to an object of type 'valhalla::midgard::GeoPoint<float>'
0x615000000800: note: object has invalid vptr
 7f 00 00 41  82 5e 3f 00 00 00 00 00  00 00 00 00 00 00 00 00  33 2e 30 2e 39 00 00 00  00 00 00 00
              ^~~~~~~~~~~~~~~~~~~~~~~
              invalid vptr
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../valhalla/baldr/nodeinfo.h:66:41 in
../src/baldr/directededge.cc:506:22: runtime error: shift exponent 4294967295 is too large for 32-bit type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/baldr/directededge.cc:506:22 in
../src/mjolnir/graphvalidator.cc:634:33: runtime error: division by zero
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/mjolnir/graphvalidator.cc:634:33 in
[          ] generating map PBF at test/data/gurka_reproduce_tile_build/2/map.pbf
[          ] building tiles in test/data/gurka_reproduce_tile_build/2
[       OK ] GraphTileBuilder.TestBuildIsReproducible (5520 ms)
[----------] 1 test from GraphTileBuilder (5520 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test suite ran. (5520 ms total)
[  PASSED  ] 1 test.

mookerji
mookerji reviewed Jul 24, 2020
View reviewed changes
Comment thread test/gurka/test_reproduce_tile_build.cc
Comment thread test/gurka/test_reproduce_tile_build.cc Outdated
Comment thread valhalla/baldr/admin.h
@merkispavel merkispavel force-pushed the consistent-tile-build branch 2 times, most recently from e01771f to 48a652e Compare July 27, 2020 10:55
@merkispavel merkispavel force-pushed the consistent-tile-build branch from 48a652e to 709cfdd Compare July 27, 2020 11:01
merkispavel
merkispavel commented Jul 27, 2020
View reviewed changes
Comment thread src/baldr/directededge.cc
if (superseded > kMaxShortcutsFromNode) {
LOG_WARN("Exceeding max shortcut edges from a node: " + std::to_string(superseded));
} else if (superseded == 0) {
superseded_ = 0;
Copy link
Copy Markdown
Contributor Author

@merkispavel merkispavel Jul 27, 2020 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is the fix of the failed build-release check a few days ago. If superseded == 0 then 1 << (superseded - 1) produces UB

@merkispavel merkispavel requested a review from mookerji July 27, 2020 11:21
merkispavel
merkispavel commented Jul 27, 2020
View reviewed changes
Comment thread src/mjolnir/graphvalidator.cc Outdated
Drop UB fix
564866d 
This fix will be committed in different PR with most UB fixes
mookerji
mookerji previously approved these changes Jul 28, 2020
View reviewed changes
Copy link
Copy Markdown
Contributor

@mookerji mookerji left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good! The Azure pipelines build is unrelated to your PR, and is failing for unrelated reasons.

@mookerji
Copy link
Copy Markdown
Contributor

mookerji commented Jul 28, 2020

@merkispavel actually I think you need to add an entry to the CHANGELOG as well, as part of this change.

@merkispavel
Copy link
Copy Markdown
Contributor Author

merkispavel commented Jul 28, 2020

@merkispavel actually I think you need to add an entry to the CHANGELOG as well, as part of this change.

Thanks for the reminder! Done

@merkispavel merkispavel merged commit bea80dc into master Jul 28, 2020
@merkispavel merkispavel deleted the consistent-tile-build branch July 28, 2020 13:35
yuzheyan added a commit that referenced this pull request Jul 28, 2020
@yuzheyan
Merge branch 'master' of github.com:valhalla/valhalla
7ed073c 
* 'master' of github.com:valhalla/valhalla:
  Make tile building reproducible (#2480)
  Fix install-script for ubuntu 18.04 (#2306) (#2486)
  nit(git): Configures changelog to resolve conflicts with union strategy (#2489)
  feat(traffictile.h): Adds versioning checks (#2484)
  Fix dereferencing of end for std::lower_bound and possible UB (#2488)
  Minor fixes to tests (#2483)
  nit: Missing changelog entry (#2478)
  Safiefy protobuf (#2477)
yuzheyan added a commit that referenced this pull request Jul 28, 2020
@yuzheyan
Merge branch 'master' into restrictioon-mm
c86c9aa 
* master:
  Make tile building reproducible (#2480)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@gknisely gknisely gknisely approved these changes

@danpaz danpaz Awaiting requested review from danpaz

+1 more reviewer

@mookerji mookerji mookerji left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

@merkispavel merkispavel

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@merkispavel @danpaz @mookerji @gknisely