Add global string de-duplication cache

[tiif]

Currently, in localtime_r and also for some cases where we raise panics, we allocate a fresh string each time. These strings never get deallocated so they just keep accumulating. Conceptually these are static strings so we can deduplicate them with a global cache.

The cache should be used everywhere that allocate_str is called with MiriMemoryKind::Machine.

[RalfJung]

(I have updated the issue title and description.)

[dev-ardi]

There exist many string interning crates, are you leaning towards any specific one?

[RalfJung]

None of them are usable I think, since the strings need to be interned in machine memory.

This should be just a FxHashMap<Vec<u8>, Pointer<Option<Provenance>>>.

[Cgettys]

Isn't this also part of a more general gap in allocate_str? For example, certain string constants in rustc const evaluation?
https://github.com/rust-lang/rust/blob/f944afe3807104803976484e7ee3aff49b6ac070/compiler/rustc_const_eval/src/util/caller_location.rs#L24
"See rust-lang/rust#89920 (comment)"
I'm guessing the performance characteristics required are different, as well as what the cache "value" should be. But thought it was worth mentioning.

Also, though currently I don't think there any current MiriMemoryKind::Machine allocate_str calls where this isn't the case, isn't an additional necessary check for interning these strings that mutability is Mutability::Not? That "seems" obvious to me, but wanted to call it out.

[RalfJung]

caller_location strings could also use the cache, yeah. In fact the entire caller_location could be cached, but it's harder to handle that with the same generic infrastructure.

And indeed, only immutable strings should be cached.

[tiif]

Initially I am thinking of removing the FIXME in

miri/src/shims/time.rs

Lines 198 to 199 in 052bdcb

	// FIXME: String de-duplication is needed so that we only allocate this string only once
	// even when there are multiple calls to this function.

But it seems that this FIXME is not resolved yet. If I understand it correctly, rust-lang/rust#127638 only added de-duplication cache for allocate_str, but alloc_os_str_as_c_str is using allocate.

Is it possible to use allocate_str for alloc_os_str_as_c_str?

[RalfJung]

Is it possible to use allocate_str for alloc_os_str_as_c_str?

No. We should have allocate_bytes which allocates a byte slice, and that should use the cache. allocate_str can call that, and transmute the result to &str.