Key Deletion and Memory Leak

[mogill]

The open-hashing scheme used to resolve key collisions means there is more than one possible place to find a key. Resolving insertion collisions is not atomic, resulting in race hazards when deletions create new places to find a key.

Deletion in EMS is implemented as overwriting the value of the key, the key itself is never freed. Although this makes insertion deterministic, it leaks memory and hash map entries. The key itself is stored on the EMS heap when the key is written, or as a result of a read-modify-write, including modification of tag bits. That is, if the key foo does not already exist, readFF("foo") will store the key foo on the EMS heap, and it is possible to consume all the entries in the hash map by reading keys that have undefined values.

In EMS 1.x the solution is to replace the open hashing scheme with hashing with chaining where collisions are resolved by chaining performed sequentially (ie: while holding a per hash element lock).

In EMS 2.x the internal heap data structure will use both hash lookup and linked lists.

[mogill]

Implement a memory allocator based on R. Marotta, M. Ianni, A. Scarselli, A. Pellegrini and F. Quaglia, "NBBS: A Non-Blocking Buddy System for Multi-core Machines," 2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID), Larnaca, Cyprus, 2019, pp. 11-20, doi: 10.1109/CCGRID.2019.00011.