Cranelift: leak in remove_constant_phis

[elliottt]

The remove_constants_phis replaces the arugments of an instruction without freeing the original list.

wasmtime/cranelift/codegen/src/remove_constant_phis.rs

Line 415 in 2cfa024

func.dfg[edge.inst].put_value_list(new_actuals);

One option for fixing this would be to build up the list to replace it as a vector, and then clearing and re-initializing the old arguments list. However, the remove_constant_phis pass might not be necessary at all after @jameysharp's refactoring of the SSA builder, so it would be good to investigate whether it's applying at all to start with.

[jameysharp]

Trevor and I were discussing this issue today. We aren't sure now whether it's safe either to free the old value-list or to overwrite it in-place.

In general, if there are multiple references to the same list, then any modification to that list based on the context of one of the references may lead to incorrect results for the other references. We had trouble with this in #3347 so last July I made cranelift-frontend copy, and potentially leak, jump-tables.

I believe the egraph optimization pass is currently assuming that value-lists referenced from instructions are not shared. That could become a source of obscure bugs. Anywhere else that modifies any EntityList could be a problem too.

I think we should collectively decide whether to allow multiple references to an EntityList in general across Cranelift.

If we do allow this, then at the least we should prevent changing the length of such lists when there might be multiple references, because if the length changes enough then the list will be reallocated at a different offset in the pool, invalidating the other references. It might be wise to prohibit modifications to value-lists entirely in this case.

But I think we should probably go the other direction, and decide that it's not okay to hold multiple references to the same EntityList. There are very few places which even could duplicate a reference: for example, git grep '\.[A-Z][A-Za-z0-9_]*(' '*.rs' is a fairly precise search for uses of instruction builders which might take an already-constructed value list, and there are very few matches. The only problem I see with this plan is that I'm not sure we can enforce it using Rust's type system, making it hard to tell if we get it wrong.

[cfallin]

But I think we should probably go the other direction, and decide that it's not okay to hold multiple references to the same EntityList

Strongly agree; implicit sharing is a recipe for ongoing future bugs, IMHO. It's quite unintuitive, in a compiler IR in general, that two separate instructions would have linked argument lists (until one understands the underlying data structures).

[jameysharp]

Looks like in #5034, @afonso360 made cranelift-fuzzgen stop reusing jump-tables too. So I think we probably don't have any cases of sharing EntityLists any more.

How could we verify that? I haven't come up with either type-system checks or runtime checks that would let us check for shared uses.

[elliottt]

We could rework the EntityList interface to no longer provide Copy and Clone, which would be a bit of work in the refactoring but would give good confidence that we're not accidentally sharing lists. Though maybe you were asking how we would determine if there are any remaining cases that would prevent that refactoring?

[jameysharp]

I guess I was just assuming that some aspect of how we use EntityList objects would prevent that plan from working. I don't know of anything off-hand though. Maybe we should just try it and find out.

[fitzgen]

This would mean that InstructionData is not copy anymore.

We could alternatively have the verifier assert that no entity list is present in more than one instruction.

[cfallin]

The verification approach seems reasonable here. I also wonder if we could, longer-term, deprecate and remove interfaces that expose EntityList directly; in theory it would be great if our API were limited to "provide slice of args" and "append arg" (and maybe "replace args with copy of this slice"). I suppose that might still entail a debug_assert on InstructionDatas fed in from outside.

[elliottt]

I think the slice interface is closer than it seems: currently we only mutate the structure of entity lists for block arguments during ssa construction, and after that everything is pretty static. #5464 removes some operations that mutate the ValueList structure for instructions, and we could probably rework ssa construction to not require mutation of the BlockCall lists anymore.