Memory leak

[Diggsey]

This is... confusing to say the least.

The following program (a minimized form of the problem I am experiencing in the wild) demonstrates what I believe to be a memory leak in DashSet.

use std::alloc::System;
use std::collections::hash_map::DefaultHasher;
use std::hash::BuildHasherDefault;

use dashmap::{DashSet, SharedValue};
use mockalloc::Mockalloc;

#[global_allocator]
static ALLOCATOR: Mockalloc<System> = Mockalloc(System);

fn run_check(offset: i32) {
    let s = DashSet::with_hasher(BuildHasherDefault::<DefaultHasher>::default());
    mockalloc::assert_allocs(|| {
        for j in 0..1000 {
            let k = (j + offset).to_string();
            let shard_index = s.determine_map(&k);
            let mut shard = s.shards()[shard_index].write();
            shard.insert(k, SharedValue::new(()));
        }
        for j in (0..1000).rev() {
            let k = (j + offset).to_string();
            let shard_index = s.determine_map(&k);
            let mut shard = s.shards()[shard_index].write();
            shard.remove(&k);
            if shard.len() * 3 < shard.capacity() {
                shard.shrink_to_fit();
            }
        }
        eprintln!("Capacity: {}", s.capacity());
    });
}

fn main() {
    run_check(9);
}

When run, the program prints the following:

Capacity: 0
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Leak',

When I trace the alloc/free calls, there is indeed a leak: the HashMap backing one of the shards is leaked. Since the capacity is zero at this time, there should not be any hashmaps still active.

When using the random hasher, the problem is difficult to reproduce which is why I switched to the default hasher, and then found a particular offset (9) which exhibits the problem.

Interestingly, I've only observed the problem with string keys. With integer keys I could not reproduce the issue.

The problem occurs exactly the same in both debug and release builds.

[Diggsey]

This turned out to be an issue with the libstd HashMap...

rust-lang/rust#79178