WEP: HashMap
Context
core:collections has one map, TreeMap<K, V>. It iterates in insertion order,
and its search tree serves only lookup: no public API reads the keys in sorted
order. Under K: Ord, a lookup costs about log₂(n) key comparisons, and a
balanced tree of any shape makes about that many.
Those comparisons are where the time goes: in a lookup-heavy program,
TreeMap<String, i32>::find_index_str takes more samples than any other
function. A B-tree in place of the AA tree speeds up insertion, removal, copying
and iteration on example/map_bench.wado, but not lookup. A hash table needs
one hash and, usually, one comparison per lookup.
A hash table brings a hazard that a tree does not have. When an attacker chooses
the keys, colliding keys turn every operation linear, which is a denial of
service. The defence is a hash keyed by a seed the attacker cannot predict.
wasi:random/insecure-seed exists for exactly that: the host hands out 128 bits
once, for hash-map seeding.
Asking the host is an effect, and a collection should not carry one. A map built
deep inside a pure function would otherwise force with InsecureSeed up through
every caller.
Decision
core:collections adds HashMap<K, V> and HashSet<T>. new() hashes under a
default seed that the host supplies once per component instance, and
with_seed takes a seed of the caller's choosing. Neither carries an effect.
The default seed, and a seed of the caller's choosing
pub struct HashSeed { k0: u64, k1: u64 }
impl HashSeed {
pub fn fixed(k0: u64, k1: u64) -> HashSeed;
}
fn host_seed() -> HashSeed with InsecureSeed {
let [k0, k1] = InsecureSeed::get_insecure_seed();
return HashSeed { k0, k1 };
}
#[benign(InsecureSeed)]
global DEFAULT_HASH_SEED: HashSeed = host_seed();
impl<K: Hash + Eq, V> HashMap<K, V> {
pub fn new() -> HashMap<K, V>; // under DEFAULT_HASH_SEED
pub fn with_seed(seed: HashSeed) -> HashMap<K, V>;
}
HashSet has the same two constructors. DEFAULT_HASH_SEED is private to
core:collections. Four things read it: new(), the literal coercions, and
the Default and Deserialize impls (below).
The seed comes from get-insecure-seed, which the host is not obliged to fill
with randomness. The interface asks to be called only once. DEFAULT_HASH_SEED
is the standard library's only caller, since HashSeed has no public way to ask
the host, and an initializer runs at most once (below). The seed never shows
through a map: iteration keeps insertion order (below), so the effect is
unobservable, which is what #[benign] asserts.
with_seed(HashSeed::fixed(…)) is for maps whose keys the program trusts and
whose hashing must be the same on every run.
#[benign] extends to globals
A global's initializer may not perform an effect
(Global Variables). #[benign(E, …)]
on a global admits the listed effects in its initializer, as it admits them in a
function body. Nothing propagates, since an initializer has no caller, and the
world import of each listed effect is still required. Only the listed effects
are admitted: an initializer that may do anything would hide I/O behind every
export.
An initializer runs outside every handler, including those installed where the
global is first read. Only a handler the initializer installs itself is in
scope, so InsecureSeed reaches the host. A handler a test installs around its
first HashMap::new() cannot pick the default seed for the whole instance.
Whether and when an initializer runs is unspecified
The order in which initializers run, and whether one runs at all, is
unspecified. Two things are guaranteed: an initializer runs at most once, and a
global's initializer has run before the global is read. A cycle among
initializers stays an error. A #[benign] global is no exception.
This replaces the rule that an initializer runs at module initialization whether
or not anything reads the global. Under the old rule DEFAULT_HASH_SEED would
ask the host for a seed, and keep the insecure-seed import, in every program
that imports core:collections, TreeMap users included. Under the new one, a
program that reaches none of its readers imports nothing for it, at every
optimization level.
eval and measure declare their effects
eval was #[benign(EvalHost)] here. Its output is the program's, so the
effect shows through the interface: eval now declares with EvalHost, and
measure declares with FuelHost. A test holds every effect, so a test calling
either declares nothing.
#[benign] is now #[ambient]
(WEP: Ambient Logging Functions).
A Kiln generator hashes under a fixed seed
Code that runs as a Kiln generator reaches DEFAULT_HASH_SEED as any other
code does. The generator world imports wasi:random/insecure-seed, whose value
may be fixed (The Sandbox), and the Kiln host
answers it from a fixed seed, so the generator stays deterministic.
This reverses an earlier decision. The Kiln host first provided no
insecure-seed, on the grounds that a fixed seed in the generator gained as
much. It did not: a generator reaching new(), a literal, Default or
Deserialize failed to compile, so code shared with ordinary programs needed a
with_seed at each map, and a struct holding a map needed a hand-written
constructor in place of a derived Default.
Iteration keeps insertion order
A HashMap iterates in insertion order, as TreeMap does. With a random seed,
any order derived from the hash would change from run to run. Insertion order
keeps a program's output the same under every seed.
Both maps keep their entries the same way: keys, values and liveness in parallel
arrays, indexed by insertion. One internal type holds them, and the two maps
differ only in the index over it, a B-tree or an open-addressing table of entry
indices. The iterators walk the entries, so the two maps and the two sets share
them: MapKeysRefIter, MapEntriesRefIter and the rest. Neither map is the
other's variant, and core:collections holds them as peers:
collections/treemap.wado, collections/hashmap.wado, and the shared
collections/entries.wado behind the facade.
Comparison reads the same entries. Two maps are equal when they hold equal
entries in the same insertion order, and order entry by entry, then by length,
as a List of pairs does. A seed, the index layout, and what was removed on the
way take no part.
Hash joins the prelude
pub trait Hasher with () {
fn write_u64(&mut self, x: u64);
fn write_bytes(&mut self, bytes: ByteSlice);
}
pub trait Hash: Eq with () {
fn hash<H: Hasher>(&self, h: &mut H);
}
Hash is bound-driven, as Eq is. It is derived for structs, variants, enums
and flags types, and written for tuples, List, String, integers, floats,
char and bool. Every implementation keeps a == b implying equal hashes, so
a written eq or cmp withholds the derived hash, which would feed members
the comparison ignores. A float's == treats every NaN as one value and -0.0
as 0.0, so its hash feeds its bits with each of those groups made one bit
pattern. f16 and bf16 hash the f32 they widen to, the value their
comparison reads. String and StrSlice hash alike, so
HashMap<String, V> offers get_str as TreeMap does.
The hash function is a seeded multiply-and-fold hash, chosen by measurement. Each word is folded into the state by a full-width multiply with a seeded key, the two halves of the product XORed together. A multiply that keeps only the low half carries a difference only upward, so the next word can cancel a difference in the top bit whatever the seed. The 64×64→128 multiply is Wasm's wide-arithmetic proposal, or a software fallback without it, so the candidates are timed as Wasm rather than taken from their native rankings. SipHash is too slow for the role.
TreeMap stays
TreeMap needs no seed, and its worst case is logarithmic. The Component Model
map<K, V> stays TreeMap
(WEP: CM map type). core:value objects,
which hold parsed external input, stay TreeMap as well.
Literals coerce, as to TreeMap and TreeSet
{ key: value, … } coerces to a HashMap<String, V>, spread included, and
[e0, e1, …] to a HashSet<T>, through the same From<Array<…>> impls
TreeMap and TreeSet carry
(WEP: Literal Coercion). A literal
names no seed, so it builds the map under DEFAULT_HASH_SEED, as new() does.
Default, Serialize and Deserialize, by hand
HashMap and HashSet implement Default, Serialize and Deserialize, each
by hand, as TreeMap and TreeSet do. The wire form is the entries alone, in
insertion order. Default and Deserialize build the map under
DEFAULT_HASH_SEED, as new() does.
None of them may be derived. Bound-driven derivation reaches private fields
across modules, so a derived Serialize would write the seed out, and a leaked
seed disables the defence. A derived Deserialize would read the seed from the
input, which is the attacker's to choose. A derived Default would hash under
an all-zero seed.
Roadmap
- [x]
HashandHasherin the prelude, with bound-driven derivation. Done when every type listed above hashes consistently with itsEq. - [ ] The hash function, chosen by measurement on Wasm.
- [x]
HashSeed,HashMapandHashSetincore:collections. Done when they offerTreeMap's andTreeSet's lookup and iteration API. - [x]
#[benign(E, …)]on a global. Done when a fixture shows the listed effects admitted in its initializer, an unlisted one still rejected, and the world import still required, and the not-yet-implemented note inspec-attributes.mdis gone. - [x] The initializer rule in
spec-expressions.md. Done when an unread global is dropped with its initializer, and the imports only it reached, at every optimization level; the fixture that pins an unread global's trapping initializer as run is replaced; and the not-yet-implemented note is gone. - [x]
DEFAULT_HASH_SEED,new()under it andwith_seed(seed)onHashMapandHashSet, andHashSeed::random()removed. Done when every caller of the oldnew(seed)has moved towith_seed, and every caller ofrandom()tonew(). - [x]
Default,SerializeandDeserializeonHashMapandHashSet. Done when aHashMap<String, V>round-trips through a JSON object in insertion order, and the output holds no seed. - [x] Map and list literals coerce to
HashMap<String, V>andHashSet<T>. Done when a literal and a spread keep source order, last write wins. - [x] The Kiln host answers
insecure-seedfrom a fixed seed. Done when a fixture's generator builds a map withnew().
Known gaps
- Every map built under
DEFAULT_HASH_SEEDin one instance shares it. A long-lived instance, such as an HTTP service, gives an attacker many requests against one seed to learn its collisions from timing. - Derivation serializes private fields of any type without a hand-written impl.
core:prng'sSeedserializes its state words this way.
