fuzzerPolygonToCellsExperimentalNoHoles times out on master: out-of-range vertex latitude produces a huge bbox estimate

[nileshpatil6]

Summary

fuzzerPolygonToCellsExperimentalNoHoles intermittently times out in the LibFuzzer clang CI job, including on pushes to master with no pull request involved. The libFuzzer artifact from one of those runs is a 33 byte input that is genuinely slow rather than hung, and it reproduces deterministically.

Evidence it hits master

Run 31322611252 (push to master, 2026-08-09):

ALARM: working on the last Unit for 432 seconds
       and the timeout value is 300 (use -timeout=N to change)
==3271== ERROR: libFuzzer: timeout after 432 seconds
SUMMARY: libFuzzer: timeout

Stack at the alarm:

#5  _ijkNormalize                 src/h3lib/include/coordijk.h:211
#6  _upAp7r                       src/h3lib/include/coordijk.h:502
#7  _faceIjkToH3                  src/h3lib/lib/h3Index.c:977
#8  vec3ToCell                    src/h3lib/lib/h3Index.c:1070
#9  latLngToCell                  src/h3lib/lib/h3Index.c:1046
#10 iterStepPolygonCompact        src/h3lib/lib/polyfill.c:467
#11 iterStepPolygon               src/h3lib/lib/polyfill.c:662
#12 polygonToCellsExperimental    src/h3lib/lib/polyfill.c:705

Reproducer

The artifact libFuzzer wrote, timeout-aa91216172a284fa214931d496dfee23b9ca0e0c:

Base64: CwAAAAAAAAAAegAAAAAAAAAA5eXl5eUj5QAAAAAAAAAA

33 bytes, which the harness decodes as:

• res = 11
• numVerts = 2
• verts[0] = lat 0, lng 6.0276e-322
• verts[1] = lat -1.61264e+179, lng 0

Feeding exactly that through the same calls the fuzzer makes, in a plain Release build with no sanitizers or coverage instrumentation:

flags=0 maxSize err=0 sz=396096 (1.88s)   polygonToCells err=0 (0.29s)
flags=1 maxSize err=0 sz=396096 (1.80s)   polygonToCells err=0 (1.03s)
flags=2 maxSize err=0 sz=396096 (1.85s)   polygonToCells err=0 (1.67s)
flags=3 maxSize err=0 sz=396096 (2.17s)   polygonToCells err=0 (2.09s)

About 13s uninstrumented for one input, which is consistent with the 432s the instrumented fuzzer binary reported. Every call returns E_SUCCESS; nothing is stuck in an infinite loop, the work is simply very large.

Why it is expensive

verts[1].lat is -1.6e179. latLngToCell only rejects non-finite coordinates:

if (!isfinite(g->lat) || !isfinite(g->lng)) {
    return E_LATLNG_DOMAIN;
}

so a finite but wildly out-of-range latitude is accepted. The bounding box derived from that vertex spans an enormous latitude range, bboxHexEstimate returns 396,096 for res 11, and the polyfill iterator walks all of it. Since the fuzzer is free to generate any 8 bytes for a latitude, inputs of this shape are reachable whenever the corpus drifts that way, which matches the intermittent CI failures.

Possible directions

I did not want to guess at intent, so rather than send a patch:

1. Clamp the polygon bounding box latitude to [-M_PI_2, M_PI_2]. Latitudes outside that range are not representable on the sphere, so this bounds the work without changing results for in-range input. It does change what comes back for out-of-range input.
2. Reject out-of-range latitude/longitude with E_LATLNG_DOMAIN in the polygonToCells entry points, rather than only rejecting non-finite values. Stricter, but a behavior change for callers who pass unnormalized coordinates today.
3. Treat it as inherent and continue managing it at the CI level, as in Increase timeout threshold for fuzzer CI run #955.

Happy to open a PR for whichever of these you prefer, or to add the artifact as a regression input if that is more useful.

Environment

• master at e9e84bd
• Reproduced on Ubuntu (WSL2), gcc, CMAKE_BUILD_TYPE=Release

[nileshpatil6]

Following up with a more precise diagnosis. The cost is not just "large input"; the resolution-coarsening guard in maxPolygonToCellsSizeExperimental silently fails on this input.

Computing the same quantities the estimator computes, for the reproducer above:

bbox north=0 south=-1.61264e+179 east=6.0276e-322 west=0
heightRads=1.61264e+179   widthRads=6.0276e-322
polygonBBoxAreaKm2 = 3.94547e-135
ratio at res 0 = 9.05453e-142   (MAX_SIZE_CELL_THRESHOLD = 10)
=> the coarsening loop never runs; estimate res stays at 11

The relevant code:

double polygonBBoxAreaKm2 =
    bboxHeightRads(polygonBBox) * bboxWidthRads(polygonBBox) /
    cos(fmin(fabs(polygonBBox->north), fabs(polygonBBox->south))) *
    EARTH_RADIUS_KM * EARTH_RADIUS_KM;

while (iter._res > 0 &&
       polygonBBoxAreaKm2 / getAverageCellArea(iter._res - 1) >
           MAX_SIZE_CELL_THRESHOLD) {
    iter._res--;
}

The bbox is effectively infinitely tall and infinitesimally wide. Multiplying those two together underflows toward zero, so a bbox that is maximally pathological is scored as having no area, the loop never decrements iter._res, and the estimate runs a full polyfill at res 11. That is where the ~1.9s per flag in the estimate goes, before polygonToCellsExperimental then does its own walk.

Two things fall out of this:

1. The heuristic uses area, but the iteration cost of a thin bbox is driven by its longer dimension. A strip one cell wide and 400k cells long has negligible area and very high cost, so area alone cannot bound the work. This is the general form of the bug and is reachable without any out-of-range coordinate, just a very thin, very tall bbox.
2. The latitude range is outside [-M_PI_2, M_PI_2] entirely. polyfill.c already carries VALID_RANGE_BBOX for a related reason at line 465. Clamping the polygon bbox latitude to that range would make the numbers sane, though on its own it does not fix the timeout here: height becomes about 1.5708 and the product still underflows, so the resolution still stays at 11.

So clamping alone is not sufficient; the coarsening criterion itself needs to account for extent per dimension, not just area. I did not want to change the estimator's behavior unilaterally, since coarsening earlier makes the estimate more conservative and therefore larger, which has knock-on effects for callers sizing buffers.

Happy to put up a PR if you can indicate which direction you prefer:

• keep area but guard against non-normal/underflowed products, and additionally bound each dimension by cells-per-side at the candidate resolution, or
• clamp the polygon bbox to the valid lat range and add the per-dimension bound, or
• something you have in mind that fits the estimator's intended contract better.