Add bounds checks for some base cell accesses #430

isaacbrodsky · 2021-02-05T05:19:57Z

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 · 2021-02-05T05:25:25Z

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 · 2021-02-05T05:44:53Z

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

isaacbrodsky · 2021-02-05T05:47:34Z

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 · 2021-02-12T00:36:42Z

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,


Should be H3_NULL?

nrabinowitz · 2021-02-12T00:39:25Z

src/h3lib/lib/h3Index.c

 */
 void _h3ToFaceIjk(H3Index h, FaceIJK* fijk) {
    int baseCell = H3_GET_BASE_CELL(h);
+    if (baseCell < 0 || baseCell >= NUM_BASE_CELLS) {  // aaa TODO


nrabinowitz · 2021-02-12T00:47:40Z

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 · 2021-02-12T00:52:31Z

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.

Add bounds checks and tests in algos, h3Index, localIj

a825535

Add exclusions for branch coverage

b4fbc82

isaacbrodsky requested review from ajfriend, dfellis and nrabinowitz February 5, 2021 05:52

8000
nrabinowitz approved these changes Feb 12, 2021

View reviewed changes

Fix TODO

b618b4a

dfellis approved these changes Feb 12, 2021

View reviewed changes

isaacbrodsky merged commit 3b5641f into uber:master Feb 12, 2021

isaacbrodsky deleted the base-cell-out-of-bounds branch February 12, 2021 18:18

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Add bounds checks for some base cell accesses #430

Add bounds checks for some base cell accesses #430

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Add bounds checks for some base cell accesses #430

Add bounds checks for some base cell accesses #430

Uh oh!

Conversation

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants