1803826 - Implement constant time casting using supertype vector

Status: RESOLVED FIXED

(Core :: JavaScript: WebAssembly, enhancement, P2)

Description

[Ryan Hunt [:rhunt] (on leave until early May)]

Wasm GC types can declare a single super type. This forms a chain of subtypes that needs to be tested for in casts. Right now this is done using a builtin and a linked list lookup (bad).

We can improve this to be constant time with extra metadata. At every cast site, we know the expected 'depth' of the type we're downcasting in the subtype chain. We can add a 'supertype vector' which we index into while downcasting to avoid a linear lookup.

This comes at the cost of some memory usage, so we should be careful to avoid n^2 blow up.

Comment 1

[Ryan Hunt [:rhunt] (on leave until early May)]

Attachment: WIP: Bug 1803826 - WIP: add WasmGcShape for keeping recursion group alive for WasmGcObject

TODO: remove canonicalization logic

Comment 2

[Ryan Hunt [:rhunt] (on leave until early May)]

Attachment: Bug 1803826 - wasm: Purge remaining type definitions at shutdown. r?yury

Before the previous commit, every WasmGcObject would have a strong
reference to the whole TypeContext of the module they were from. The
TypeContext would then release RecGroup's carefully so that we were
able to also free them from the canonical type set precisely.

After the previous commit, every WasmGcObject keeps a strong reference
to just the recursion group they're from. This makes it much harder
to ensure that we clean up every entry in the canonical type without
expensive loops or locking solutions.

I don't think this is an immediate issue, as this only affects modules
using GC types where their objects routinely outlive the module they're
from. This commit removes the assertion in TypeIdSet and adds a note
for future work to improve this.

Depends on D164019

Comment 3

[Ryan Hunt [:rhunt] (on leave until early May)]

Attachment: Bug 1803826 - wasm: Replace RttValue with a pointer to TypeDef. r?jseward

This commit removes RttValue and replaces it with a const wasm::TypeDef*
field. RttValue's only purpose was to keep the recursion group alive, and
to contain the pointer to the TypeDef.

The shape for WasmGcObject's now keeps the recursion group alive, and we
can now replace the RttValue with the TypeDef pointer directly.

Depends on D164020

Comment 4

[Ryan Hunt [:rhunt] (on leave until early May)]

Attachment: Bug 1803826 - wasm: Add SuperTypeVector to TypeDef for constant time subtyping checks. r?jseward

This commit adds extra metadata to enable constant time subtyping checks.

This metadata is a display vector of all super types for a given type that
we index into instead of iterating over a linked list. A comment tries to
explain this in more detail.

Depends on D164021

Comment 5

[Ryan Hunt [:rhunt] (on leave until early May)]

Attachment: Bug 1803826 - wasm: Emit subtype checks inline in baseline. r?jseward

This commit adds an inline version of TypeDef::isSubtypeOf to MacroAssembler
and uses it in baseline for GC instructions.

Depends on D164022

Comment 6

[Ryan Hunt [:rhunt] (on leave until early May)]

The first commit is WIP, as that may depend on bug 1804253. I also still have to add support to Ion, as that now supports downcasting as well.

Comment 7

[Ryan Hunt [:rhunt] (on leave until early May)]

Attachment: Bug 1803826 - wasm: Emit subtype checks inline in ion. r?jseward

The equivalent patch to the baseline patch. This is done by adding a
single MIR node, MWasmGcObjectIsSubtypeOf, which is used as a direct
replacement for calls to Instance::refTest.

This commit specializes the lowering of MWasmGcObjectIsSubtypeOf when
it is used in a MTest for effecient branching.

Depends on D164023

Comment 8

[Ryan Hunt [:rhunt] (on leave until early May)]

Attachment: Bug 1803826 - wasm: Add recursion group to WasmGCShape. r?jandem

This commit adds a wasm::RecGroup* pointer to WasmGCShape that is
used to keep the recursion group, and therefore the type definition
of a wasm GC object alive. The pointer to the type definition will
be stored as a second header word on the object.

This is a bit tricky because we'd like to keep shape's the same size
and there's not room for another pointer. This commit takes the
approach of re-using the field where the NativeObject property map
is stored. I first tried to use a union for this, but ran into an
issue around non-trivial destructors in unions for the GCPtr. To
workaround this, this commit restructures the shape kinds to define
their own final field. NativeShape has a prop map, WasmGCShape has
a rec group.

Comment 9

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/536bbd3588b7
wasm: Add recursion group to WasmGCShape. r=jandem
https://hg.mozilla.org/integration/autoland/rev/7a6967540909
wasm: Purge remaining type definitions at shutdown. r=yury
https://hg.mozilla.org/integration/autoland/rev/3c3cf8dcf6f3
wasm: Replace RttValue with a pointer to TypeDef. r=jseward
https://hg.mozilla.org/integration/autoland/rev/a2ca5f570e02
wasm: Add SuperTypeVector to TypeDef for constant time subtyping checks. r=jseward
https://hg.mozilla.org/integration/autoland/rev/dcb589432f2f
wasm: Emit subtype checks inline in baseline. r=jseward
https://hg.mozilla.org/integration/autoland/rev/776663bd80ae
wasm: Emit subtype checks inline in ion. r=jseward
https://hg.mozilla.org/integration/autoland/rev/0f9ef9ff3fea
1803826, 1803826, 1803826, 1803826, 1803826: apply code formatting via Lando

Comment 10

[Iulian Moraru]

https://hg.mozilla.org/mozilla-central/rev/536bbd3588b7
https://hg.mozilla.org/mozilla-central/rev/7a6967540909
https://hg.mozilla.org/mozilla-central/rev/3c3cf8dcf6f3
https://hg.mozilla.org/mozilla-central/rev/a2ca5f570e02
https://hg.mozilla.org/mozilla-central/rev/dcb589432f2f
https://hg.mozilla.org/mozilla-central/rev/776663bd80ae
https://hg.mozilla.org/mozilla-central/rev/0f9ef9ff3fea