search

ziglang / zig

General-purpose programming language and toolchain for maintaining robust, optimal, and reusable software.
https://ziglang.org
MIT License
34.48k stars 2.52k forks source link

std.AutoHashMap: randomize the hash to surface the bug of relying on hash order #13115

Open andrewrk opened 2 years ago

andrewrk commented 2 years ago

In debug builds, auto hash functions should additionally munge the user-provided hash values by a random number in order to reveal the bug of relying on hash order.

Instead of std.crypto.random, a seed should be used so that determinism of debugging is maintained. An example of a nice seed would be the pointer address of the hash map. This will be the same for multiple runs of the same binary assuming ASLR is off but will change often enough to catch bugs in reliance on traversal order. Additionally it will not introduce a dependency on thread local storage.

This is not necessary for AutoArrayHashMap which maintains insertion order.

Vexu commented 2 years ago

Is the order observable for any other operation besides iteration? If not we could make the iterator randomly swap the order of two entries.

An example of a nice seed would be the pointer address of the hash map.

This would require pinning the hash map since copying it would break all the hashes.

andrewrk commented 2 years ago

That sounds like an excellent idea to me. Great point about the pinning issue.