Store one status byte per bucket in WTF::HashTable
Component: WTF HashTable | 53bedf6
Source/WTF/wtf/HashMap.h
Source/JavaScriptCore/dfg/DFGLazyJSValue.cpp
WTF::HashTable is the open-addressing table behind HashMap, HashSet and many internal caches (atom strings, DFG CSE, JIT thunks, DOM caches). Each key type used to reserve two sentinel values, empty and deleted, that stored keys could never equal, and the table recorded bucket state by writing those values into buckets. A translator lets callers look up and insert with a different type than the stored key, and its translate() fills in the new bucket; since the bucket held a valid sentinel, translators could simply assign into it.
The table now keeps a separate status byte per bucket (empty, deleted, or seven bits of the key's hash), and lookups scan that byte array before touching bucket storage. Per-type sentinels are no longer needed, so a fresh bucket's memory can be truly uninitialized, and translators across JSC, WTF and WebCore now take a T* to raw storage and construct in place.
Before: After:
buckets[]: key/value pairs status[]: 1 byte per bucket
empty = sentinel key 0x00 = empty
deleted = sentinel key 0x01 = deleted
lookup loads full bucket/probe 0x80|h7 = full, 7 hash bits
translate(T& slot, ...) translate(T* raw, ...)
slot = value (assign over new (NotNull, raw) T(value)
sentinel)
Significance
Speedometer 3 improves by about 1%, MotionMark by 0.5% and JetStream 3 by up to 0.8%, because misses and collisions resolve within one cache line. It also removes the long-standing class of bugs around reserved sentinel key values. The flip side, per the commit message, is that assigning into a fresh bucket is now much more likely to hit real garbage bits.
Audit directions
- Any translator the commit missed (out-of-tree, GTK/WPE/Win, lesser-used ones) that still assigns a refcounted type (
String,RefPtr,Weak) into raw storage would release a stale, attacker-influenced pointer, a classic UAF or type-confusion primitive. - Exception safety and re-entrancy in
translate(): if construction throws or re-enters the same table (functor()inensure, Weak/GC callbacks), a bucket may be marked full before it is constructed, or the table may rehash mid-insert. - Ordering between
status[]and bucket data across add, remove, rehash, shrink and destruction, including deleted-to-empty transitions, tombstone accounting, and 7-bit tag collisions combined with the table-size-scaled index bits. - Tables JSC reads off the main thread (DFG compiler threads, GC marking, concurrent JIT) could see torn visibility between status and bucket data, or depend on changed iteration order.
- Keys that used to be illegal (
nullptr, 0, -1) are now valid; code that used a sentinel as "absent", or relied on removedisValidKey()assertions (SmallMap), may now behave differently. - Size and overflow handling for the status-plus-buckets allocation layout, and the copied iterators in
RobinHoodHashTable, which still uses sentinels.