Switch to direct-mapped indirect-call cache.

[cfallin]

Currently, the indirect-call cache operates on a basis of one slot per callsite: each call_indirect instruction in a module, up to a limit, has its own slot of storage in the VM context struct that caches a called-table-index to called-raw-function-pointer mapping.

This is fine but means the storage requirement scales with the module size; hence "up to a limit" above. It also means that each callsite needs to "warm up" separately, whereas we could in theory reuse the resolved index->code pointer mapping for the same index across callsites.

This PR switches instead to a "direct-mapped cache": that is, we have a fixed number of cache slots per table per instance, of user-configurable count, and we look in a slot selected by the called table index (modulo the cache size). As before, if the "tag" (cache key, called table index) matches, we use the "value" (raw code pointer).

The main advantage of this scheme, and my motivation for making the switch, is that the storage size is fixed and quite small, even for arbitrarily-large modules: for example, on a 64-bit platform with 12-byte slots(*) (4-byte key, 8-byte resolved pointer), for a module with one funcptr table, a 1K-entry cache uses 12KiB per instance. That's much smaller than the total VMFuncRef array size in large modules and should be no problem. My goal in getting to this constant size offset is that turning this on by default eventually will be easier to justify, and that we won't have unexpected perf cliffs for callsites beyond a certain index.

This also means that if one callsite resolves index 23 to some raw code pointer, other callsites that call index 23 also receive a "hit" from that warmup. This could be beneficial when there are many callsites but a relatively smaller pool of called functions (e.g., ICs).

The downside to caching indexed on callee rather than callsite is that if there are a large number of callees, we can expect more cache conflicts and hence misses. (If funcref table indices 1 and 1025 are both frequently called, a 1024-entry direct-mapped cache will thrash.) But I expect with ICs in particular to have a lot of callsites and relatively few (shared) callees.

On Octane-compiled-to-Wasm with my JS AOT compilation tooling using call_indirect for all ICs, I see: baseline score (higher is better, proportional to runtime speed) of 2406, score with old one-entry-per-callsite scheme of 2479, score with this scheme of 2509. So it's slightly faster as well, probably due to a combination of the warmup benefit and a smaller cache footprint, even with the more involved logic to compute the slot address. (This also tells me the benefit of this cache is smaller than I had originally measured on a microbenchmark (20%) -- at 5% on all of Octane -- but that's still worth it, IMHO.)

() Note that slots are not actually contiguous: I did a struct-of-arrays trick, separating cache tags from cache values, so that the assembly lowering can use scaling amodes (`vmctx + offset + 4idxfor u32 accesses, and8*idx` for u64 accesses) for more efficient code.

[github-actions[bot]]

Subscribe to Label Action

cc @fitzgen

This issue or pull request has been labeled: "fuzzing", "wasmtime:api", "wasmtime:config", "wasmtime:ref-types" Thus the following users have been cc'd because of the following labels: * fitzgen: fuzzing, wasmtime:ref-types To subscribe or unsubscribe from this label, edit the .github/subscribe-to-label.json configuration file. [Learn more.](https://github.com/bytecodealliance/subscribe-to-label-action)

[github-actions[bot]]

Label Messager: wasmtime:config

It looks like you are changing Wasmtime's configuration options. Make sure to complete this check list:

• [ ] If you added a new Config method, you wrote extensive documentation for it.

  Our documentation should be of the following form: ```text Short, simple summary sentence. More details. These details can be multiple paragraphs. There should be information about not just the method, but its parameters and results as well. Is this method fallible? If so, when can it return an error? Can this method panic? If so, when does it panic? # Example Optional example here. ```

• [ ] If you added a new Config method, or modified an existing one, you ensured that this configuration is exercised by the fuzz targets.

  For example, if you expose a new strategy for allocating the next instance slot inside the pooling allocator, you should ensure that at least one of our fuzz targets exercises that new strategy. Often, all that is required of you is to ensure that there is a knob for this configuration option in [`wasmtime_fuzzing::Config`][fuzzing-config] (or one of its nested `struct`s). Rarely, this may require authoring a new fuzz target to specifically test this configuration. See [our docs on fuzzing][fuzzing-docs] for more details.

• [ ] If you are enabling a configuration option by default, make sure that it has been fuzzed for at least two weeks before turning it on by default.

---

To modify this label's message, edit the .github/label-messager/wasmtime-config.md file. To add new label messages or remove existing label messages, edit the .github/label-messager.json configuration file. [Learn more.](https://github.com/bytecodealliance/label-messager-action)

[alexcrichton]

Er I actually flubbed the test a bit and discovered a bug I didn't mean to discover. This is what I intended:

(module
  (func (export "_start")
    i32.const 1 ;; not 0 unlike above
    call_indirect
    i32.const 1 ;; not 0 unlike above
    call_indirect (result i32)
    drop
  )

  (func $a)

  (table 10 10 funcref)
  (elem (offset (i32.const 1)) func $a)
)

which runs successfully with -O cache-call-indirects but fails without it due to a signature mismatch error. This is what I was trying to reproduce above and is my comment about how the cache key needs to take the tag into account as well. Otherwise though I'm not actually sure what the segfault above is, but that might be more benign.

---

Out of curiosity I was also curious, had I not caught this, if fuzzing would catch it. Forcing differential execution of Wasmtime-against-Wasmtime and module generation with wasm-smith this isn't showing up after ~10 minutes of 30 cores fuzzing. This might be something where cache-call-indirects isn't getting a hit on the fuzz modules being configured (does it require the table min == max? I forget...). Basically our fuzz coverage of this may not be that great right now (although oss-fuzz is generally better about coverage than local runs)

[cfallin]

Notably I think that the cache key can't just be the index but must also be the type used as well? I'm not sure how much the load of the VMSharedTypeIndex will affect perf, so I figure it's probably best to figure this out first before diving too deep in review.

Ah, could you say more why the type is necessary? In my (possibly naive) view, we are choosing the cache slot to look at a different way, but nothing else should change (obviously there is some breakage here which I'll take a look at -- team meeting next two days so slight delay).

[alexcrichton]

The behavior of call_indirect is dependent on the table being used, the runtime index, and the type ascribed on call_indirect, but the implementation here only takes two of these into account. The caches are per-table (I think? I didn't dive that deep) and the cache key handles the runtime index. Basically the previous behavior would implicitly take all three into account by having a cache-per-callsite. This implementation has where multiple call sites can share the same cache slot (intentional) but if each call site has different types ascribed to the call_indirect then they have to have different behavior.

The basic tl;dr; though is that this PR as-is violates wasm-semantics and isn't memory safe. (insofar that you can successfully call a function with the wrong signature)

[cfallin]

Ah, I completely missed the dynamic signature check -- will have to incorporate that probably by baking it into the cache key somehow. (I don't think we'll need a load on the hot path at all.) Solution TBD, thanks!

[cfallin]

Excellent finds on both -- fixes pushed to (i) tag cache entries with signature ID as well, (ii) check for null code pointer (the feature on main also doesn't catch this; not sure why fuzzing hasn't hit it yet). It's late so I'll test perf tomorrow. Hopefully still a win: the key advantage here should be avoiding the dependent cache misses inherent in the two-level pointer chase of the VMFuncRef, but this is an objective question I can answer concretely soon :-)

[cfallin]

On testing the newest version of this PR, that correctly keeps a cache tag for signature ID and also correctly checks for null(*), I'm now seeing a 2.5% slowdown on Octane in AOT JS relative to no caching at all. So it seems this has crossed the instruction-count tradeoff threshold (the benchmarks have quite high IPC so it's about bulk of instruction stream, not cache misses).

Given the smaller delta I'm seeing now with indirect-call caching in full benchmarks, vs. the microbenchmark I was using to guide me at the time, I think I will actually opt to remove indirect-call caching altogether: the null handling in main's version is also incorrect (see footnote below) and I'd rather not have the complexity, perf cliff on module size, and vmctx size overhead if it's worth relatively little.

(*) I had previously incorrectly remembered the SIGSEGV-for-call-to-null-funcref mechanism as working by catching a call to address 0; actually it works by catching a SIGSEGV on a load from the VMFuncRef, so the caching mechanism here would not catch that (and would "safely" crash wasmtime at least, rather than execute type-unsafely, but that's still wrong).