`RandomState` with the `std` feature enabled doesn't produce random seeds on new threads

[hoxxep]

Hey @orlp,

Because of OS thread caching and the thread_local counter, calls to gen_per_hasher_seed can repeatedly start at the same stack address on cached/reused threads, generating the same seed on reused threads. I've built a significant overhaul to rapidhash's seeding in hoxxep/rapidhash#98 in case it's useful as a reference, specifically on the seeding.rs changes. I'd be curious if you have any thoughts on making it cleaner or more robust, since we're both re-solving the same issue.

I'm also happy to port some of the logic from rapidhash's seeding into foldhash, but would need to know which bits you like/dislike. Numbering the conceptual changes:

1. Seed generation (hot path):
   1. For std, with-atomics: I use a global AtomicUsize counter with get/set, similar to the no-std atomic ptr branch, but only run when the thread_local! is instantiated for the first time.
   2. For no-std, with-atomics: Removed a folded multiply step from the no-std atomic-ptr branch for an increment.
   3. For no-std, no-atomics: Added getrandom_03 and getrandom_04 gated branches for embedded and WASM platforms. I try to avoid getrandom in the hot seed generation path.
2. Global secret generation (cold path, prefer a stronger seed):
   1. For getrandom: Added getrandom_03 and getrandom_04 to generate the global secrets. Prefer this for a good global starting seed.
   2. For std, no-getrandom: use std's std::hash::RandomState to source initial randomness when std is enabled.
   3. For no-std, no-getrandom: rely solely on ASLR.
   4. Removed the OS time randomisation (as it's no longer necessary/available).

I've separated the getrandom features to enable versioning the getrandom crate independently from the hash, while keeping support for MSRV 1.71.

Running the following code in seed.rs with the std feature enabled demonstrates the issue, on my M1 Max machine I see 4/1024 unique seeds.

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_seed_collision_is_unlikely_across_threads() {
        extern crate std;
        use std::collections::BTreeSet;

        const THREADS: usize = 1024;
        let seeds: BTreeSet<u64> = (0..THREADS)
            .map(|_| std::thread::spawn(gen_per_hasher_seed).join().unwrap())
            .collect();

        // If threads are seeded uniquely, we should see THREADS unique seeds.
        assert_eq!(seeds.len(), THREADS, "only {}/{} unique seeds", seeds.len(), THREADS);
    }
}

Cheers!

[orlp]

I don't want to make a lot of changes right now. I think the issue you're showing here is legitimate and I should incorporate the suggestion of initializing the thread-local better.