array types (fixed-size arrays on 32-bit, HashMap, Vec) can be large enough that indexing is unsound

[thestinger]

In a 32-bit process running on a 64-bit operating system, it's possible to allocate a Vec<u8> of length 1u32 << 31 or greater. The maximum value where uint as int produces a positive number is (1u32 << 31) - 1), so int is not large enough for offset operations to the end of these vectors. Everything from the language's built-in slice indexing operations to the push method on Vec<T> will perform an invalid negative (backwards) offset as the getelementptr instruction uses a signed offset.

[thestinger]

I think the solution to this problem is defining the maximum size of an object or array type to be the maximum positive value representable by int. This would make using int for these cases correct, and the only loss would be the inability to have an object larger than half the address space which does not seem important. This would be a clear value to use as the upper bound on type sizes (which is now implemented, but without a language defined upper bound) and could also be an upper bound on the maximum size returned by memory allocators. It could be implemented deep inside jemalloc's huge allocation handling where it would have no performance impact.

[thestinger]

The non-jemalloc memory allocation support would need to branch in allocate and reallocate, but it would be optimized out in all but cases where the sizes are dynamic (like vectors). Custom allocators would also need to consider this issue, but it can be very clearly laid out in the documentation.

[petrochenkov]

The problem is not exactly about size of allocations, for example a large bit container like Bitv can allocate less than int::MAX bytes of memory, but its index difference will still overflow. So the language requirement about size of allocations needs to be supplemented with library requirements on sizes of containers.

[thestinger]

@petrochenkov: This issue is about undefined behaviour from pointer arithmetic overflows, including in low-level language primitives like struct field offsets and indexing of fixed-size arrays. Fixing it requires both lowering the max object size on 32-bit and dealing with pointer arithmetic overflows in collections. The Bitv integer overflow issues are entirely separate from this, as are integer overflows in collections of zero-size types.

[thestinger]

Rust, like C and C++, uses the inbounds marker on pointer arithmetic instructions for performance reasons. Pointer arithmetic instructions that wrap have undefined behaviour with inbounds. Rust needs to bound the size of all types to prevent these overflows via the basic language primitives.

That's what the pull request I opened about this does, and now the remaining problems with pointer arithmetic overflows in library collections need to be fixed. It can either be done by adding code deep inside the allocator where it will have zero overhead or by adding pervasive overflow checks that will be hard to get right and will hurt performance. I don't think bounding individual memory allocations from liballoc to half of the address space is a major sacrifice to make for simplicity and performance.

[petrochenkov]

@petrochenkov: I see, that means I misinterpreted the "unsound" in the title, i.e. overflow in Bitv is still dangerous, but it is not unsound in the memory safety sense.