prevent size overflows in the type system

[thestinger]

Type size calculations inside the compiler can overflow, resulting in memory unsafety. Types without a valid mem::size_of should be forbidden to prevent unsoundness. Types that are valid today would become invalid and this would interfere with an attempt to support integer type parameters. I think it's a serious backwards compatibility issue since the interaction with generics is very bad.

std::mem::size_of::<[[u8, ..!0u], ..!0u]>() returns 1, since !0u * !0u wraps to 1. The same thing can be done with other aggregate types like structs / tuples and an overflow could also occur from the tag added in an enum.

[zwarich]

Here's an example of a simple program that segfaults on x86_64 OS X:

fn main() {
    let n = 0u;
    let a = box [&n,..0xF000000000000000u];
    println!("{}", a[0xFFFFFFu]);
}

[thestinger]

This seems to indicate that Rust can't correctly type-check generics from the definition alone. It needs to be aware of the type parameters in order to check for size overflows. Sizes are platform specific due to issues like alignment so valid types are platform specific.

[arielb1]

@thestinger

If a type has a size overflow then it can't exist, as it can't fit in memory. If you try to place it on the stack, you would get a stack overflow. This is, and should, be handled within trans.

[thestinger]

@arielb1: You're misunderstanding the issue. A type will a size overflow can certainly be created, as demonstrated by the example @zwarich gave. The size of the type has overflowed, so it's possible to create it because not enough space will be reserved. The problem is not limited to fixed-size arrays and can't be handled solely during initialization. The existence of the types actually needs to be considered invalid.

[arielb1]

@thestinger

Certainly they can be created now (due to the bug) – however, they should not be creatable (given that they take all address space). I think making size_of::<T> give a trans error when sizeof(T)>INT_MAX would be fine (its not like its impossible to make trans error out with resource limitations anyway).

[thestinger]

The problem isn't limited to mem::size_of. It's a general issue with size overflows in the compiler. There's no size_of call in @zwarich's example and it's not hard to think up new ways of hitting this.

[thestinger]

The size calculation code inside of the compiler (underlying size_of and lots of other code paths) could error out in this case, but I expect that it wouldn't be enough to prevent this in all cases. There are other ways of initializing data (uninit and init among others) that are used to build higher level safe abstractions. There's an expectation that every type corresponds to a valid representation, whether or not it can actually be created in practice.

[nikomatsakis]

@thestinger I agree, we should be careful in the trans paths, but it seems like ultimately this can be handled by checking for overflow in various places when constructing the LLVM version of a Rust type. e.g., when constructing an array type, we'd check that the size of the base type * the length doesn't overflow and so forth. Do you disagree?

[thestinger]

@nikomatsakis: The logic can be in trans, but it's not as simple as checking at construction of an array (multiplication overflow) / struct (addition overflow) / enum (addition overflow from the tag). For example, consider the init and uninit intrinsics or creating a struct with box.

[arielb1]

The overflow actually seems to happen within LLVMSizeOfTypeInBits aka llvm::DataLayout::getTypeSizeInBits (which is called from rustc::middle::trans::machine::llsize_of_real) – which makes this LLVM's issue.

This can be observed by noticing that the following program prints 0:

fn main() {
    println!("{}", std::mem::size_of::<[u8, ..(1<<61)]>());
}

Note that the size is 1<<61 bytes, not 1<<64 as would be expected (also, on 32-bit architectures, trans::intrinsic L242 reduces sizes to a uint – which seems bad, especially because this is a compiler uint, not a target uint, but the 64-bit overflow is totally LLVM's fault).

[eddyb]

#17795 seems like it could cause related issues.

[thestinger]

@arielb1: That's an unrelated issue, not the type system issue here. The issue I've reported here cannot occur with a fixed size array of u8. It isn't a specific flaw in the implementation and isn't restricted to cases where Rust calculates a size. I gave an example of an incorrect size_of result because it's an easy way of demonstrating the problem, not because it is the source of the issue.

[arielb1]

@thestinger

Rust outsources the size calculations to several LLVM methods, including LLVMSizeOfTypeInBits, and the overflows in calculating type sizes occur within LLVM, and can be demonstrated via the following program (which segfaults):

fn main() {
    let s : [u8, ..(1<<61)] = [0, ..(1<<61)];
    if s[0] == 0 { unreachable!() }
}

Types with a size that can't be represented in a uint are just uninhabited types, not much different from enum Void {} in semantics, and certainly not a by-design soundness hole. Being uninhabited, operations with them are all fine, but are almost always trivial (actually I'm quite sure we can have size_of<Uninhabited>() == 0 for all uninhabited types without causing any trouble). Because the operations are trivial, it does not matter which offsets rustc calculates, as if you have a value of an uninhabited type you are already in UB territory.

EDIT:

Value constructors (e.g. [T, ..N]) certainly can't successfully construct uninhabited types, but the current implementations may overwrite memory before they fail. We need to make these aborts (in trans) in these cases.

[thestinger]

The fixed-size array case was just an example, and there are other ways of turning this into a vulnerability. A size calculation is not necessary to trigger a bug with this.

[nikomatsakis]

@thestinger can you elaborate on what you think will go wrong relating to the init intrinsic etc that would not be protected by checking in trans that the size of aggregate types do not overflow? It seems to me that, when monomorphizing, we must eventually try to construct the actual type that will cause the overflow, and hence could detect the overflow at that time. Also, do you have a preferred way to address this?

[thestinger]

@nikomatsakis: We could detect it at any point where the type could be constructed but size calculations would need to be moved into Rust. If it's actually forbidden at compile-time rather than via an error at runtime, then it's a change in semantics because it will impact code generated via generics / macros but that's never actually called.

[arielb1]

I'm investigating this.

It seems that size calculations are already halfway-in-Rust-halfway-in-LLVM, so this shouldn't be too bad.

[nikomatsakis]

@thestinger OK. Regarding it being a change in semantics, I suppose that's technically true, but I don't think it's something we need to get too excited about. It's quite the edge case. I'd personally be inclined to just make it fail compilation eagerly rather than panic at runtime. But it's not a big thing and I could be persuaded the other way. Naturally it's a shame to repeat all size calculation on the Rust size, it'd be nice to avoid that.

[pnkfelix]

Assigning P-backcompat-lang, 1.0.