Debugging: refactor stack frame cursor into frame handle abstraction. (#12566)

* Debugging: refactor stack frame cursor into frame handle abstraction.

This addresses some of the issues described #1

Debugging: refactor stack frame cursor into frame handle abstraction. (#12566)

* Debugging: refactor stack frame cursor into frame handle abstraction.

This addresses some of the issues described #12486: we need the ability
to keep a handle to a stack frame as long as execution is frozen, and
keep multiple of these handles around, alongside the `Store`, without
any handle directly holding a borrow of the store.

The frame handles work by means of an "execution version" scheme: the
idea is that whenever any execution resumes in a given store, all
handles to existing frames could be invalidated, but if no such
execution occurs, all handles should still be valid. A tuple of
(globally unique for process lifetime) store ID, and execution version
within that store, should be sufficient to uniquely identify any
frozen-stack period during execution. This accomplishes cheap handle
invalidation without the need to track existing handles.

This PR also implements a cache of parsed frame-table data. Previously
this was lazily parsed by the cursor as it walked up a stack, but with
multiple handles hanging around, and with handles meant to be cheap to
hold and clone, and with handles being invalidated eagerly, it makes
much more sense to persist this parsed metadata at the `Store` level.
(It cannot persist at the `Engine` level because PCs are local per
store.)

* Re-bless disas tests (offsets in VMStoreContext changed).

* Handle invalidation tests.

* Review comments, and make API return `Result`s rather than panic'ing on stale handles.

* Review feedback.

* Doc-comment link fix.

* Review feedback.

* cfg-gate Activation method to `debug` feature only.

* Fix unused-import warning in no-debug cfg.

* Fix doc link (again, after rename from latest feedback).

show more ...

refactor recursive reentrance checks (#12349)

* refactor recursive reentrance checks

This commit makes a few changes related to recursive reentrance checks, instance
poisoning, etc.:

- Implements

refactor recursive reentrance checks (#12349)

* refactor recursive reentrance checks

This commit makes a few changes related to recursive reentrance checks, instance
poisoning, etc.:

- Implements the more restrictive lift/lower rules described in https://github.com/WebAssembly/component-model/pull/589 such that a component instance may not lower a function lifted by one of its ancestors, nor vice-versa. Any such lower will result in a fused adapter which traps unconditionally, preventing guest-to-guest recursive reentrance without requiring data flow analysis.
- Note that this required updating several WAST tests which were violating the new rule, including some in the `tests/component-model` Git submodule, which I've updated.
- This is handled entirely in the `fact` module now; I've removed the `AlwaysTrap` case previously handled by `wasmtime-cranelift`.
- Removes `FLAG_MAY_ENTER` from `InstanceFlags`. It is no longer needed for guest-to-guest calls due to the above, and for guest-to-host-to-guest calls we can rely on either `FLAG_NEEDS_POST_RETURN` for sync-lifted functions or the `GuestTask` call stack for async-lifted functions.
- Adds a `StoreOpaque::trapped` field which is set when _any_ instance belonging to that store traps, at which point the entire store is considered poisoned, meaning no instance belonging to it may be entered. This prevents indeterminant concurrent task state left over from the trapping instance from leaking into other instances.

Note that this does _not_ include code to push and pop `GuestTask` instances for
guest-to-guest sync-to-sync calls, nor for host-to-guest calls using e.g. the
synchronous `Func::call` API, so certain intrinsics which expect a `GuestTask`
to be present such as `backpressure.inc` will still fail in such cases. I'll
address that in a later PR.

Also note that I made a small change to `wasmtime-wit-bindgen`, adding a `Send`
bound on the `T` type parameter for `store | async` functions. This allowed me
to recursively call `{Typed}Func::call_concurrent` from inside a host function,
and it doesn't have any downsides AFAICT.

Fixes #12128

* bless bindgen expansions

* bless disas tests

* address review feedback

* sync `trap.h` with `trap_encoding.rs`

...and add const assertions to `trap.rs` to help avoid future divergence.

show more ...

Cranelift: Rewrite conditional branches to unconditional traps into conditional traps during legalization (#10988)

* Cranelift: Legalize via a backwards walk, rather than forwards

Note: the test ex

Cranelift: Rewrite conditional branches to unconditional traps into conditional traps during legalization (#10988)

* Cranelift: Legalize via a backwards walk, rather than forwards

Note: the test expectation change in `filetests/egraph/misc.clif` is simply
because we happen to change the order in which we created the legalized
`stack_addr` instructions that get GVN'd together, and therefore also changed
their relative value numbering. We dedupe to the value that occurs first in the
function, which is the one inserted into the DFG *after* the other now because
of the backwards traversal, and it therefore has a different value number from
before. The resulting program is identical, modulo value numbering.

* Cranelift: Rewrite conditional branches to unconditional traps into conditional traps during legalization

Given this instruction:

```clif
brif v0, block1, block2
```

If we know that `block1` does nothing but immediately trap then we can rewrite
that `brif` into the following:

```clif
trapz v0, <trapcode>
jump block2
```

(And we can do the equivalent with `trapz` if `block2` immediately traps).

This transformation allows for the conditional trap instructions to be GVN'd and
for our egraphs mid-end to generally better optimize the program. We
additionally have better codegen in our backends for `trapz` than branches to
unconditional traps.

Fixes https://github.com/bytecodealliance/wasmtime/issues/10941

* Update CLIF filetests and Wasmtime disas tests

show more ...

Cranelift: egraphs: fix a few sources of exponential rewrite blowup. (#10579)

This arrived as a fuzzbug [1] with some very interesting optimization
behavior. The test case has sequences of `(select

Cranelift: egraphs: fix a few sources of exponential rewrite blowup. (#10579)

This arrived as a fuzzbug [1] with some very interesting optimization
behavior. The test case has sequences of `(select _ x x)` operators --
that is, conditional selects with both inputs the same -- that are
chained together sequentially. A few aspects of the egraph framework and
our optimization rules conspired to create exponential blowup:

- We have a rewrite rule for `(select _ x x) -> x`, but we do not
subsume; this means that we create an eclass for both. This in itself
is not a problem; however...

- We have some *other* rules that look through the inputs to the select
to detect other cases (e.g.: select between constants 1 and 0, or 0
and 0, or ...), so we traverse both inputs;

- And we also do nested rewrites, so when the rewrite rule for `(select
_ x x) -> x` fires, and the `x` is itself another select in a long
chain of selects, we traverse all possible paths (through first
or second args) to the roots. In effect we get an eclass that has the
ultimate root and then 2^n combinations of `select` nodes on top of
that.

This got worse with the recent change to canonicalize less (for
simpler/cheaper compilation), hence the fuzzbug timeouts.

This PR includes a few fixes, all complementary to each other:

- The `(select _ x x) -> x` rule now subsumes; this is another case
where we have a strictly better rewrite and so we should short-circuit
the eclass blowup.

- The rewrite runner sorts and dedups returned value numbers; in
debugging the above I noticed we were getting two rules producing the
same rewritten value and we were adding the same value twice with two
union nodes.

- The rewriter keeps a total eclass size per root and limits the total
eclass size to a fixed limit (currently 5). We thus now have limits in
three different axes: depth of eager rewrites (5); number of returned
matches (also 5); and total size of eclass (5). The first two don't
necessarily imply the third because we otherwise can keep unioning on
top of an eclass and (as seen above) see exponential blowup.

[1]: https://oss-fuzz.com/testcase-detail/4806924172591104

show more ...

Reuse Wasm linear memories code for GC heaps (#10503)

* Reuse code for Wasm linear memories for GC heaps

Instead of bespoke code paths and structures for Wasm GC, this commit makes it
so that we no

Reuse Wasm linear memories code for GC heaps (#10503)

* Reuse code for Wasm linear memories for GC heaps

Instead of bespoke code paths and structures for Wasm GC, this commit makes it
so that we now reuse VM structures like `VMMemoryDefinition` and bounds-checking
logic. Notably, we also reuse all the associated bounds-checking optimizations
and, when possible, virtual-memory techniques to completely elide them.

Furthermore, this commit adds support for growing GC heaps, reusing the
machinery for growing memories, and makes it so that GC heaps always start out
empty. This allows us to properly delay allocating the GC heap's storage until a
GC object is actually allocated.

Fixes #9350

* fix c api compilation

* use assert_contains

* remove no-longer-necessary extra memory config from limiter tests

* Helper for retry-after-maybe-async-gc in libcalls

* Clean up some comments

* fix wasmtime-fuzzing and no-gc compilation

* fix examples

* fix no-gc+compiler build

* fix build without pooling allocator

* fix +cranelift +gc-drc -gc-null builds

* fix table hash key stability test

* fix oracle usage of `ExternRef::new`

* fix +gc -gc-null -gc-drc build

* fix wasmtime-fuzzing

* make `StorePtr` wrap a `NonNull`

* Fix some doc tests

* Remove some unnecessary retry helpers now that `FooRef::new` will auto-gc

* fix things after rebase

* Reorganize collection/growth methods for GC heap

* rename BoundsCheck variants

* fix cfg'ing of gc only code

* Fix doc tests

* fix one more gc cfg

* disable GC heap OOM test on non-64-bit targets

show more ...

Cranelift: simplify some side-effectful instructions in ISLE (#10524)

* Cranelift: simplify some side-effectful instructions in ISLE

This commit adds a new top-level ISLE entrypoint specifically fo

Cranelift: simplify some side-effectful instructions in ISLE (#10524)

* Cranelift: simplify some side-effectful instructions in ISLE

This commit adds a new top-level ISLE entrypoint specifically for instructions
in the side-effectful skeleton: `simplify_skeleton`. While these rewrites are
processed during the egraph pass, values from skeleton instructions still do not
get inserted into the egraph. Indeed, `simplify_skeleton` operates
on *instructions* rather than *values* because we do not represent side effects
as values; values do not have side effects in CLIF, instructions do. Therefore,
rather than doing a whole dynamic-programming style extraction of the best
candidate simplification like we do with the egraph, we take an eager and greedy
approach.

Furthermore, `simplify_skeleton` is limited only to skeleton instructions that
do not involve control-flow or terminators right now. This is because changing
the control-flow graph can change whether a use is dominated by a def or not,
and we do not currently have the machinery to track and fix up invalidated
uses. Addressing this is left for future commits.

* fix `MIN / -1` cprop and add negative tests for things simplify_skeleton cannot handle yet

show more ...

Add "pure" flag to `ir::MemFlags` (#10340)

* Add "pure" flag to `ir::MemFlags`

This flag represents whether the memory operation's safety (e.g. the validity of
its `notrap` and `readonly` claims) i

Add "pure" flag to `ir::MemFlags` (#10340)

* Add "pure" flag to `ir::MemFlags`

This flag represents whether the memory operation's safety (e.g. the validity of
its `notrap` and `readonly` claims) is purely a function of its data
dependencies.

If this flag is `true`, then it is okay to code motion this instruction to
arbitrary locations, in the function, including across blocks and conditional
branches, so long as data dependencies (and trap ordering, if relevant) are
upheld.

If this flag is `false`, then the memory operation's safety potentially relies
upon invariants that are not reflected in its data dependencies, and therefore
it is not safe to code motion this operation. For example, this operation could
be in a block that is dominated by a control-flow bounds check that makes this
operation safe, and that invariant is not reflected in its operands. It would be
unsafe to code motion such an instruction above its associated bounds check,
even if its data dependencies would still be satisfied.

I've added this flag because we were doing exactly that kind of code motion
where we moved a `readonly` and `notrap` memory operation past its associated
null-check and therefore it was no longer safe to perform and we would get a
segfault. This could only be triggered when the Wasm typed-function-references
proposal was enabled, which is not a tier-1 proposal, so it is not considered a
vulnerability. Nonetheless, it is a pretty scary kind of bug, and other code
paths weren't affected due to pretty subtle interactions. And this is the
motivation for the new "pure" flag: without needing to explicitly opt into
data-dependency-based code motion (i.e. set the "pure" flag), it is too easy to
accidentally move loads past their control-flow-based safety guards.

* fix load-hoisting test; also test that non-pure loads don't hoist

* Rename `pure` flag to `can_move`

show more ...

Cranelift: dedupe `trap[n]z` instructions (#10004)

* Cranelift: dedupe `trap[n]z` instructions

This commit extends our existing support for merging idempotently side-effectful
instructions that pro

Cranelift: dedupe `trap[n]z` instructions (#10004)

* Cranelift: dedupe `trap[n]z` instructions

This commit extends our existing support for merging idempotently side-effectful
instructions that produce exactly one value to those that produce zero or one
value, and marks the `trap[n]z` instructions as having idempotent side
effects. This cleans up a lot test cases in our `disas` test suite, particularly
those related to explicit bounds checks and GC.

As an aside, it seems like it should be easy to extend this to idempotently
side-effectful instructions that produce multiple values as well, but I don't
believe we have any such instructions, so I didn't bother.

* Update more disas tests

* review feedback

show more ...

Shuffle fields in `VMRuntimeLimits` (#9739)

* Shuffle fields in `VMRuntimeLimits`

Right now this structure has a pointer-sized field, two 64-bit integers,
and then three pointer-sized fields. This

Shuffle fields in `VMRuntimeLimits` (#9739)

* Shuffle fields in `VMRuntimeLimits`

Right now this structure has a pointer-sized field, two 64-bit integers,
and then three pointer-sized fields. This structure's layout is
nontrivial to calculate on 32-bit platforms as it needs to take the
alignment of 64-bit integers into account which differs between ARM and
x86 for example. To make this easier shuffle all the 64-bit integers are now
first, which means we don't have to worry about alignment.

I'll note that this particular ordering is still a bit brittle because
we might need to shuffle things again if more fields are added. That
being said any misalignment is caught during testing of the `wasmtime`
crate so there's not much danger in adding more things, it'll just
require updating a few more locations.

* Update test expectations

show more ...

Add the "null" garbage collector (#9484)

* Add the "null" garbage collector

The null collector does not actually collect any garbage, it simply
bump-allocates until the heap is exhausted, at which

Add the "null" garbage collector (#9484)

* Add the "null" garbage collector

The null collector does not actually collect any garbage, it simply
bump-allocates until the heap is exhausted, at which point further allocation
attempts will fail. It does not require any GC barriers.

Users can configure which collector to use via the `wasmtime::Config::collector`
method or the `-C collector=drc|null` CLI flag. The `wasmtime::Collector` enumeration,
similar to the `wasmtime::Strategy` enumeration but for choosing a collector
rather than a compiler, additionally has a table summarizing the properties and
characteristics of our current set of collector implementations.

Finally, we also run `.wast` tests that exercise GC types under both the DRC and
null collectors. I tried to avoid running tests that are not related to GC under
both configurations just to avoid a combinatorial blow up.

* cargo fmt

* fix +gc -gc-null -gc-drc build

* Fix some warnings in various cargo feature combo builds

* Fix some more warnings in certain build configs

* Fix unit tests for null GC

* Fill in some placeholder comments that I forgot to write

* Fix issues where we ask for a GC store when we don't actually need one

Which was causing test failures, since we no longer return a GC store with a
dummy heap.

* Add fuzzing config support for different collectors

* address review feedback

* fix cmake tests

* Fix test compilation after rebase

* Fix GC tests under MIRI

show more ...