Can't retain a scalar that's inline in a mutable collection

This is kind of an ugly architectural issue I discovered recently. I don't think it's been seen in the wild.

The bug

1. Create a mutable Array or Dict
2. Add a bool or a small (<2048) int to it. A very short string might do this too.
3. Get item 0 from the collection as a Value
4. Retain it

Result: UBSan warnings about unaligned pointers, followed by an ASan fatal buffer overrun error. If sanitizers aren't enabled, you probably crash with heap corruption sometime later.

What's Going On

A value in a mutable container is stored in a ValueSlot, either inline or as a pointer. Small scalars (7 bytes or less) are stored inline. On little-endian CPUs, inline values are offset by 1 byte so that the first byte can be a 0xFF tag which marks it as inline. (If it were a pointer, this would be the low byte, which would be even since it's malloced.) That means an inline scalar Value has an odd address.

Unfortunately, an odd address usually denotes a heap-allocated mutable Value, i.e. a larger scalar or a collection. The HeapValue class deliberately offsets its embedded Value by one byte to ensure this. This is how Value::isMutable works.

The problem is that retaining a value [in HeapValue::retain] first checks isMutable; if so, it casts it to HeapValue and calls retain() on that. This incorrectly happens when the value is an inline scalar; but since it isn't actually a HeapValue, this ends up incrementing a 32-bit int 5 bytes before the Value, which is guaranteed to corrupt something. Ouch.

Workaround

Don't call FLValue_Retain on a value that might be a small scalar in a mutable collection.

Band-Aid Fix

I have a patch that doesn't really fix the problem, but at least allows you to tell that an inline scalar isn't itself mutable, and will cause the Retain call to throw an exception instead of corrupting data.

• Store a different tag byte value in a ValueSlot than in a HeapValue
• Value::isMutable checks this byte, and returns false for an inline scalar value
• The Retain call detects the inline scalar and throws an InvalidData exception with the message "Can't retain scalar Value %p that's inline in a mutable container". There is a lengthy explanation in a comment just above the line where this is thrown.

A Real Fix?

Instead of throwing an exception, the Retain call should cast the Value to a ValueSlot pointer, then (somehow) find the ValueSlot's owning mutable collection, then retain that.

The "(somehow)" is the hard part. ValueSlot is intentionally tiny, 8 bytes. Adding a pointer back to its owner would double its size. But there's not really any other way to find it! The ValueSlots are the elements of either a vector or an unordered_map owned by the HeapValue.

Start by reproducing the sanitizer failure with a bool or small integer in a mutable Array or Dict, then read Value::isMutable, HeapValue::retain, and ValueSlot. Compare the inline-scalar and HeapValue representations and the vector or unordered_map ownership described in the issue. Done means retaining an inline scalar no longer corrupts memory and its lifetime is handled correctly.