Implement our OOM-handling SecondaryMap from scratch

[fitzgen]

I realized we need to adjust its V: Clone bound into V: TryClone which means
that we can no longer actually just wrap an inner
cranelift_entity::SecondaryMap<K, V> and need to instead implement our
own. This also made me realize that we need remove to be fallible because,
when the entry being removed is in bounds, it overwrites the entry with the
default value, but that default value needs to be TryCloned now which is, of
course, a fallible operation.

Depends on

• Implement TryClone for Arc<T>, Option<T>, and Result<T, E> #12615
• Implement TryClone for GcLayout #12616
• Implement TryClone for PackedOption #12617
• Implement TryClone for RegisteredType and RecGroupEntry in the types registry #12619
• Add a clear method to our OOM-handling Vec #12620

[alexcrichton]

I'll be honest in that I continue to not really understand SecondaryMap as a data structure as it seems so niche to almost never be applicable... Do we actually have any usages of the map which need this TryClone bound? Could we, for example, switch this a Copy bound on the key?

[github-actions]

Subscribe to Label Action

cc @fitzgen

Details

This issue or pull request has been labeled: "cranelift", "fuzzing", "wasmtime:api", "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.

[fitzgen]

I'll be honest in that I continue to not really understand SecondaryMap as a data structure as it seems so niche to almost never be applicable...

It is for whenever you want to associate extra data with a PrimaryMap's key on the side (sort of struct-of-arrays style), and it also supports use cases where potentially not every key has extra data / there is a default value for the extra data.

For example, in the TypeRegistry we (morally) have a PrimaryMap<VMSharedTypeIndex, Arc<WasmSubType>> but we also want to be able to map from a type to its GC layout, if any, so we have a SecondaryMap<VMSharedTypeIndex, Option<GcLayout>> on the side as well.

Do we actually have any usages of the map which need this TryClone bound? Could we, for example, switch this a Copy bound on the key?

The key is already bounded by EntityRef, which implies Copy. The TryClone bound is for values. And yes, we do have non-Copy values in SecondaryMaps that need to be try_cloned (such as GcLayout in the previous example).

[cfallin]

It is for whenever you want to associate extra data with a PrimaryMap's key on the side (sort of struct-of-arrays style), and it also supports use cases where potentially not every key has extra data / there is a default value for the extra data.

To say it another way that may also help (I've had this question too in the past):

• PrimaryMaps manage/allocate the ID space, and are dense (Vec internally);
• SecondaryMaps are given existing IDs, and are dense;
• HashMaps, the other corner in common use, are given existing IDs and are sparse.

So in Cranelift we tend to use them where we know most IDs will have an entry. Using a PrimaryMap would be incorrect as it would allocate different IDs.