Skip to content

Add bounds checks for some base cell accesses#430

Merged
isaacbrodsky merged 3 commits into
uber:masterfrom
isaacbrodsky:base-cell-out-of-bounds
Feb 12, 2021
Merged

Add bounds checks for some base cell accesses#430
isaacbrodsky merged 3 commits into
uber:masterfrom
isaacbrodsky:base-cell-out-of-bounds

Conversation

@isaacbrodsky

@isaacbrodsky isaacbrodsky commented Feb 5, 2021

Copy link
Copy Markdown
Collaborator

Partial update of #423 with tests (thanks @alexey-milovidov). These fix potential crashes (segfault) or otherwise out of bounds reads. I did not port two of the checks in baseCells.c since I could not readily test them. They could be added in a future PR.

Benchmark results (release configuration, recent MacBook Pro)
Before

% make benchmarks
[  9%] Formatting sources
[  9%] Built target format
[ 36%] Built target h3
[ 45%] Built target benchmarkH3Line
Scanning dependencies of target bench_benchmarkH3Line
	-- h3LineNear: 16.212100 microseconds per iteration (10000 iterations)
	-- h3LineFar: 700.057000 microseconds per iteration (1000 iterations)
[ 45%] Built target bench_benchmarkH3Line
[ 54%] Built target benchmarkPolygon
Scanning dependencies of target bench_benchmarkPolygon
	-- pointInsideGeofenceSmall: 0.034070 microseconds per iteration (100000 iterations)
	-- pointInsideGeofenceLarge: 0.295750 microseconds per iteration (100000 iterations)
	-- bboxFromGeofenceSmall: 0.027170 microseconds per iteration (100000 iterations)
	-- bboxFromGeofenceLarge: 0.322950 microseconds per iteration (100000 iterations)
[ 54%] Built target bench_benchmarkPolygon
[ 63%] Built target benchmarkH3SetToLinkedGeo
Scanning dependencies of target bench_benchmarkH3SetToLinkedGeo
	-- h3SetToLinkedGeoRing2: 59.360300 microseconds per iteration (10000 iterations)
	-- h3SetToLinkedGeoDonut: 22.918100 microseconds per iteration (10000 iterations)
	-- h3SetToLinkedGeoNestedDonuts: 95.143400 microseconds per iteration (10000 iterations)
[ 63%] Built target bench_benchmarkH3SetToLinkedGeo
[ 63%] Built target benchmarkH3Api
Scanning dependencies of target bench_benchmarkH3Api
	-- geoToH3: 0.687900 microseconds per iteration (10000 iterations)
	-- h3ToGeo: 0.422600 microseconds per iteration (10000 iterations)
	-- h3ToGeoBoundary: 2.132000 microseconds per iteration (10000 iterations)
[ 63%] Built target bench_benchmarkH3Api
[ 72%] Built target benchmarkVertex
Scanning dependencies of target bench_benchmarkVertex
	-- cellToVertexes: 2.287000 microseconds per iteration (10000 iterations)
	-- cellToVertexesPent: 0.090400 microseconds per iteration (10000 iterations)
	-- cellToVertexesRing: 31.332400 microseconds per iteration (10000 iterations)
	-- cellToVertexesRingPent: 35.073900 microseconds per iteration (10000 iterations)
[ 72%] Built target bench_benchmarkVertex
[ 81%] Built target benchmarkKRing
Scanning dependencies of target bench_benchmarkKRing
	-- kRing10: 7.425000 microseconds per iteration (10000 iterations)
	-- kRing20: 26.990900 microseconds per iteration (10000 iterations)
	-- kRing30: 58.684600 microseconds per iteration (10000 iterations)
	-- kRing40: 100.795300 microseconds per iteration (10000 iterations)
	-- kRingPentagon10: 213.414000 microseconds per iteration (500 iterations)
	-- kRingPentagon20: 1768.964000 microseconds per iteration (500 iterations)
	-- kRingPentagon30: 5831.160000 microseconds per iteration (50 iterations)
	-- kRingPentagon40: 13730.700000 microseconds per iteration (10 iterations)
[ 81%] Built target bench_benchmarkKRing
[ 90%] Built target benchmarkH3UniEdge
Scanning dependencies of target bench_benchmarkH3UniEdge
	-- getH3UnidirectionalEdgeBoundary: 5.064700 microseconds per iteration (10000 iterations)
[ 90%] Built target bench_benchmarkH3UniEdge
[100%] Built target benchmarkPolyfill
Scanning dependencies of target bench_benchmarkPolyfill
	-- polyfillSF: 1203.760000 microseconds per iteration (500 iterations)
	-- polyfillAlameda: 1664.290000 microseconds per iteration (500 iterations)
	-- polyfillSouthernExpansion: 54339.300000 microseconds per iteration (10 iterations)
[100%] Built target bench_benchmarkPolyfill
Scanning dependencies of target benchmarks
[100%] Built target benchmarks

After

% make benchmarks
[  9%] Formatting sources
[  9%] Built target format
[ 36%] Built target h3
[ 45%] Built target benchmarkH3UniEdge
	-- getH3UnidirectionalEdgeBoundary: 4.853900 microseconds per iteration (10000 iterations)
[ 45%] Built target bench_benchmarkH3UniEdge
[ 54%] Built target benchmarkH3Line
	-- h3LineNear: 14.541700 microseconds per iteration (10000 iterations)
	-- h3LineFar: 688.441000 microseconds per iteration (1000 iterations)
[ 54%] Built target bench_benchmarkH3Line
[ 63%] Built target benchmarkPolygon
	-- pointInsideGeofenceSmall: 0.035170 microseconds per iteration (100000 iterations)
	-- pointInsideGeofenceLarge: 0.293390 microseconds per iteration (100000 iterations)
	-- bboxFromGeofenceSmall: 0.027260 microseconds per iteration (100000 iterations)
	-- bboxFromGeofenceLarge: 0.308790 microseconds per iteration (100000 iterations)
[ 63%] Built target bench_benchmarkPolygon
[ 72%] Built target benchmarkH3SetToLinkedGeo
	-- h3SetToLinkedGeoRing2: 60.570600 microseconds per iteration (10000 iterations)
	-- h3SetToLinkedGeoDonut: 22.946600 microseconds per iteration (10000 iterations)
	-- h3SetToLinkedGeoNestedDonuts: 95.399400 microseconds per iteration (10000 iterations)
[ 72%] Built target bench_benchmarkH3SetToLinkedGeo
[ 72%] Built target benchmarkH3Api
	-- geoToH3: 0.654900 microseconds per iteration (10000 iterations)
	-- h3ToGeo: 0.412700 microseconds per iteration (10000 iterations)
	-- h3ToGeoBoundary: 2.152000 microseconds per iteration (10000 iterations)
[ 72%] Built target bench_benchmarkH3Api
[ 81%] Built target benchmarkVertex
	-- cellToVertexes: 2.062300 microseconds per iteration (10000 iterations)
	-- cellToVertexesPent: 0.067100 microseconds per iteration (10000 iterations)
	-- cellToVertexesRing: 30.586400 microseconds per iteration (10000 iterations)
	-- cellToVertexesRingPent: 35.477500 microseconds per iteration (10000 iterations)
[ 81%] Built target bench_benchmarkVertex
[ 90%] Built target benchmarkPolyfill
	-- polyfillSF: 1206.176000 microseconds per iteration (500 iterations)
	-- polyfillAlameda: 1686.132000 microseconds per iteration (500 iterations)
	-- polyfillSouthernExpansion: 53059.800000 microseconds per iteration (10 iterations)
[ 90%] Built target bench_benchmarkPolyfill
[100%] Built target benchmarkKRing
	-- kRing10: 8.776000 microseconds per iteration (10000 iterations)
	-- kRing20: 27.379200 microseconds per iteration (10000 iterations)
	-- kRing30: 59.835500 microseconds per iteration (10000 iterations)
	-- kRing40: 102.880500 microseconds per iteration (10000 iterations)
	-- kRingPentagon10: 204.118000 microseconds per iteration (500 iterations)
	-- kRingPentagon20: 1792.512000 microseconds per iteration (500 iterations)
	-- kRingPentagon30: 5691.240000 microseconds per iteration (50 iterations)
	-- kRingPentagon40: 13445.700000 microseconds per iteration (10 iterations)
[100%] Built target bench_benchmarkKRing
[100%] Built target benchmarks

From the benchmarks, h3ToGeo, h3ToGeoBoundary, and kRing do not seem to be significantly impacted. I don't think we have a benchmarking setup that is capable of detecting very small changes in performance, but there is no large change.

@dfellis

dfellis commented Feb 5, 2021

Copy link
Copy Markdown
Collaborator

Are you sure before and after are in the right order there? Every single benchmark improves slightly when I compare the two (fewer microseconds per iteration). You'd expect testing noise to vary up and down.

@coveralls

coveralls commented Feb 5, 2021 •
edited
Loading

Copy link
Copy Markdown

Coverage Status

Coverage increased (+0.07%) to 99.315% when pulling b618b4a on isaacbrodsky:base-cell-out-of-bounds into b04c78f on uber:master.

@isaacbrodsky

isaacbrodsky commented Feb 5, 2021

Copy link
Copy Markdown
Collaborator Author

I reran and got:
Before

[  9%] Formatting sources
[  9%] Built target format
[ 36%] Built target h3
[ 45%] Built target benchmarkH3Line
	-- h3LineNear: 14.370600 microseconds per iteration (10000 iterations)
	-- h3LineFar: 680.556000 microseconds per iteration (1000 iterations)
[ 45%] Built target bench_benchmarkH3Line
[ 54%] Built target benchmarkH3SetToLinkedGeo
	-- h3SetToLinkedGeoRing2: 59.014600 microseconds per iteration (10000 iterations)
	-- h3SetToLinkedGeoDonut: 22.934500 microseconds per iteration (10000 iterations)
	-- h3SetToLinkedGeoNestedDonuts: 94.997500 microseconds per iteration (10000 iterations)
[ 54%] Built target bench_benchmarkH3SetToLinkedGeo
[ 54%] Built target benchmarkH3Api
	-- geoToH3: 0.607400 microseconds per iteration (10000 iterations)
	-- h3ToGeo: 0.422700 microseconds per iteration (10000 iterations)
	-- h3ToGeoBoundary: 2.082600 microseconds per iteration (10000 iterations)
[ 54%] Built target bench_benchmarkH3Api
[ 63%] Built target benchmarkPolygon
	-- pointInsideGeofenceSmall: 0.036960 microseconds per iteration (100000 iterations)
	-- pointInsideGeofenceLarge: 0.304230 microseconds per iteration (100000 iterations)
	-- bboxFromGeofenceSmall: 0.028300 microseconds per iteration (100000 iterations)
	-- bboxFromGeofenceLarge: 0.327700 microseconds per iteration (100000 iterations)
[ 63%] Built target bench_benchmarkPolygon
[ 72%] Built target benchmarkVertex
	-- cellToVertexes: 2.224400 microseconds per iteration (10000 iterations)
	-- cellToVertexesPent: 0.086900 microseconds per iteration (10000 iterations)
	-- cellToVertexesRing: 30.551200 microseconds per iteration (10000 iterations)
	-- cellToVertexesRingPent: 35.017000 microseconds per iteration (10000 iterations)
[ 72%] Built target bench_benchmarkVertex
[ 81%] Built target benchmarkKRing
	-- kRing10: 8.078300 microseconds per iteration (10000 iterations)
	-- kRing20: 27.012000 microseconds per iteration (10000 iterations)
	-- kRing30: 58.415900 microseconds per iteration (10000 iterations)
	-- kRing40: 100.714000 microseconds per iteration (10000 iterations)
	-- kRingPentagon10: 210.714000 microseconds per iteration (500 iterations)
	-- kRingPentagon20: 1771.128000 microseconds per iteration (500 iterations)
	-- kRingPentagon30: 5804.460000 microseconds per iteration (50 iterations)
	-- kRingPentagon40: 13695.400000 microseconds per iteration (10 iterations)
[ 81%] Built target bench_benchmarkKRing
[ 90%] Built target benchmarkH3UniEdge
	-- getH3UnidirectionalEdgeBoundary: 5.151000 microseconds per iteration (10000 iterations)
[ 90%] Built target bench_benchmarkH3UniEdge
[100%] Built target benchmarkPolyfill
	-- polyfillSF: 1213.938000 microseconds per iteration (500 iterations)
	-- polyfillAlameda: 1670.652000 microseconds per iteration (500 iterations)
	-- polyfillSouthernExpansion: 52924.700000 microseconds per iteration (10 iterations)
[100%] Built target bench_benchmarkPolyfill
[100%] Built target benchmarks

After

[  9%] Formatting sources
[  9%] Built target format
[ 36%] Built target h3
[ 45%] Built target benchmarkH3Line
	-- h3LineNear: 14.138800 microseconds per iteration (10000 iterations)
	-- h3LineFar: 684.242000 microseconds per iteration (1000 iterations)
[ 45%] Built target bench_benchmarkH3Line
[ 54%] Built target benchmarkPolygon
	-- pointInsideGeofenceSmall: 0.036520 microseconds per iteration (100000 iterations)
	-- pointInsideGeofenceLarge: 0.336960 microseconds per iteration (100000 iterations)
	-- bboxFromGeofenceSmall: 0.031540 microseconds per iteration (100000 iterations)
	-- bboxFromGeofenceLarge: 0.331070 microseconds per iteration (100000 iterations)
[ 54%] Built target bench_benchmarkPolygon
[ 63%] Built target benchmarkH3SetToLinkedGeo
	-- h3SetToLinkedGeoRing2: 58.942600 microseconds per iteration (10000 iterations)
	-- h3SetToLinkedGeoDonut: 22.969300 microseconds per iteration (10000 iterations)
	-- h3SetToLinkedGeoNestedDonuts: 95.647500 microseconds per iteration (10000 iterations)
[ 63%] Built target bench_benchmarkH3SetToLinkedGeo
[ 63%] Built target benchmarkH3Api
	-- geoToH3: 0.660200 microseconds per iteration (10000 iterations)
	-- h3ToGeo: 0.400000 microseconds per iteration (10000 iterations)
	-- h3ToGeoBoundary: 2.151000 microseconds per iteration (10000 iterations)
[ 63%] Built target bench_benchmarkH3Api
[ 72%] Built target benchmarkVertex
	-- cellToVertexes: 2.158700 microseconds per iteration (10000 iterations)
	-- cellToVertexesPent: 0.086000 microseconds per iteration (10000 iterations)
	-- cellToVertexesRing: 30.760900 microseconds per iteration (10000 iterations)
	-- cellToVertexesRingPent: 36.240700 microseconds per iteration (10000 iterations)
[ 72%] Built target bench_benchmarkVertex
[ 81%] Built target benchmarkKRing
	-- kRing10: 8.391800 microseconds per iteration (10000 iterations)
	-- kRing20: 30.850600 microseconds per iteration (10000 iterations)
	-- kRing30: 59.733900 microseconds per iteration (10000 iterations)
	-- kRing40: 103.647700 microseconds per iteration (10000 iterations)
	-- kRingPentagon10: 206.004000 microseconds per iteration (500 iterations)
	-- kRingPentagon20: 1791.200000 microseconds per iteration (500 iterations)
	-- kRingPentagon30: 5907.340000 microseconds per iteration (50 iterations)
	-- kRingPentagon40: 13537.400000 microseconds per iteration (10 iterations)
[ 81%] Built target bench_benchmarkKRing
[ 90%] Built target benchmarkH3UniEdge
	-- getH3UnidirectionalEdgeBoundary: 5.144700 microseconds per iteration (10000 iterations)
[ 90%] Built target bench_benchmarkH3UniEdge
[100%] Built target benchmarkPolyfill
	-- polyfillSF: 1333.394000 microseconds per iteration (500 iterations)
	-- polyfillAlameda: 1749.352000 microseconds per iteration (500 iterations)
	-- polyfillSouthernExpansion: 54871.300000 microseconds per iteration (10 iterations)
[100%] Built target bench_benchmarkPolyfill
[100%] Built target benchmarks

I would imagine it's being influenced by other things running on the computer.

nrabinowitz
nrabinowitz approved these changes Feb 12, 2021
View reviewed changes
Comment thread src/apps/testapps/testH3ToParent.c
"Invalid resolution fails");
t_assert(H3_EXPORT(h3ToParent)(child, 15) == 0,
"Invalid resolution fails");
t_assert(H3_EXPORT(h3ToParent)(child, 16) == 0,

@nrabinowitz nrabinowitz Feb 12, 2021 •
edited
Loading

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

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

Should be H3_NULL?

Comment thread src/h3lib/lib/h3Index.c Outdated
*/
void _h3ToFaceIjk(H3Index h, FaceIJK* fijk) {
int baseCell = H3_GET_BASE_CELL(h);
if (baseCell < 0 || baseCell >= NUM_BASE_CELLS) { // aaa TODO

@nrabinowitz nrabinowitz Feb 12, 2021

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

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

Kill TODO?

@nrabinowitz

nrabinowitz commented Feb 12, 2021

Copy link
Copy Markdown
Collaborator

As discussed offline, I think we should have a separate PR that's a bit more paranoid about protecting against segfaults in baseCell.c, rather than relying on the caller of each function to assume responsibility for bounds checks.

@isaacbrodsky

isaacbrodsky commented Feb 12, 2021

Copy link
Copy Markdown
Collaborator Author

As discussed offline, I think we should have a separate PR that's a bit more paranoid about protecting against segfaults in baseCell.c, rather than relying on the caller of each function to assume responsibility for bounds checks.

I'll approach that in a separate PR. I think as a longer term evolution, once we have a clearer error handling story at the public API level, we can propagate error codes within the library too and avoid some of the potentially duplicated checking of base cell validity. Right now that duplication is essentially required by the need to return error codes which is a bigger change for baseCells.c.

@isaacbrodsky isaacbrodsky merged commit 3b5641f into uber:master Feb 12, 2021
@isaacbrodsky isaacbrodsky deleted the base-cell-out-of-bounds branch February 12, 2021 18:18
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@nrabinowitz nrabinowitz nrabinowitz approved these changes

@dfellis dfellis dfellis approved these changes

@ajfriend ajfriend Awaiting requested review from ajfriend

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@isaacbrodsky @dfellis @coveralls @nrabinowitz