Skip to content

WorkerWrapper.call needs more entropy #97

@martinhath

Description

@martinhath

Thanks for the library!

class WorkerWrapper {
    call(i) {
        return new Promise((resolve, reject) => {
            i.id = Math.floor(Math.random() * 100000);
            this.promises[i.id] = { resolve, reject };
            this.gdalWorker.postMessage(i);
        });
    }
}

The WorkerWrapper.call method generates an id for each message sent to the worker, but there's no check to see if concurrent calls have overlapping ids. The current domain for ids is [0, 100000), which is pretty low due to the birthday paradox, where the chance of collision is surprisingly high.

Using this online birthday problem calculator and plugging in D=100_000 and P=0.5 we get the number of in-flight requests we can have before the chance of a collision is at least 50%, and the answer is 373(!). For 10%, the answer is 146.

This can happen in applications, for instance if you fetch data from a bunch of map tiles over a reasonably large area (quickly getting >100 tiles), and then using gdal to decode some map data, for instance vector data. The result is that some promises just never resolve. This happens because the first promise's calbacks are never called, as it was overwritten by a second promise that got the same id. The resolve callback for that promise is then called twice.

Suggested fix

  • Increase the max id to MAX_SAFE_INTEGER. This is less arbitrary than 100_000 and it should behave similarly. The calculator says the number of in-flight requests required to get a 1% chance of collision is more than 10 million, which is probably okay.
  • Check for collisions, and generate a new id if we collide. Remove the promise from the map after it's resolved to decrease the chance of generating a used id.

Idk if step (2) is reeeeaally necessary after having done step (1), but why risk collisions when we can trivially avoid it?

I don't know this codebase at all, so there might be things I'm missing here. Otherwise, I'd be happy to contribute a PR to fix this.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions