Should `null().add(0)` work?

[mcy]

This question comes up a lot in C/C++ land. Here is the status quo:

• C rejects the program NULL + 0 as ill-formed, because arithmetic must land inside of an "allocation".
• C++ accepts NULL + 0, by special case, an defines it to be NULL.
• LLVM defines getelementptr inbounds T, T* 0, i64 0 to be T* 0, again by special case.
  • Incidentally, Clang lowers p + 0 to getelementptr inbounds in both language modes.
• Rust rejects the program ptr::null::<T>().add(0), for the same reasons as C.
  • Miri correctly rejects it as UB (Miri seems to special-case null here? Am I reading this right?)

IME this has caused quite a bit of pain in C, where you might want to write:

void Foo(char* p, size_t len) {
  char* end = p + len;
  for(; p != end; p++) { ... }
}

This is UB for any sensible choice of an empty slice, including p = NULL. While Rust gives us the tools to avoid writing such code, it is... somewhat questionable to follow C rather than C++ here. Like, you could use wrapping_add(), but honestly that seems a bit silly given that LLVM goes out of its way to make this work, and to my knowledge Clang's frontend doesn't care except for -fsanitize=null.

I get the impression this wasn't a conscious decision and more of an emergent property of "you can only do add() on valid pointers", but it'd be nice to document it if it was. Although you could infer that p != NULL if you write p + n in a vaccum, I've never seen a situation where being able to deduce this is useful optimization fuel. That said, I would not mind being proven wrong for when I have equivalent conversations in C/C++ land. =)

[mcy]

Addendum: Miri accepts the following correct program:

let slice = std::slice::from_raw_parts(0x1 as *const u8, 0);  // Valid alternate spelling of &[].
let range = slice.as_ptr_range();  // Calls ptr.add(len) internally.

So yeah, it seems Miri is special-casing NULL + 0 intentionally. =/

[Lokathor]

0x1 isn't null though.

[mcy]

My point is that Miri rejects (0 as *mut u8).add(0) but not (1 as *mut u8).add(0). It does reject (1 as *mut u8).add(1). Something seems wrong here. I would be willing to accept this for a ZST (in the "there exist infinitely many ZSTs at every well-aligned address" sense) but it seems very odd in the non-ZST case.

[Lokathor]

With ptr::add, you can start and end one byte past an allocated object. So if you start at one byte past an allocated object then add 0, you're still one byte past the end, and thus you're fine.

but if you start at one byte past the end and add 1 you've gone too far and it's UB.

[RalfJung]

I think this is a duplicate of #93: basically, I wish I knew what the exact rules in LLVM were here, so that we can ensure Rust is following those rules. But sadly, the LangRef is far from clear, and when I asked for clarification I did not get clear answers either.

So currently, Miri accepts (1 as *mut u8).add(0) because otherwise the standard library is horribly unsound, but rejects (0 as *mut u8).add(0) because LLVM seems pretty clear that this is not allowed. Miri also rejects ptr.add(0) when ptr points to some allocation that was previously allocated but has since been freed (this is based on the provenance of the pointer).

For non-0 offsets, like in (1 as *mut u8).add(1), I think there is no question: this is definitely disallowed, since there would have to be an allocation of size at least 1 here to accept this. Only .add(0) is interesting.

If I could have my way, .add(0) would just be always allowed. But sadly LLVM does not seem to give us that option.

[RalfJung]

Btw, in case you are curious, here is the code that implements this in Miri:

https://github.com/rust-lang/rust/blob/7d8e7b14a7ccfeca85f7206c0a7e27a3f144ce9e/compiler/rustc_mir/src/interpret/intrinsics.rs#L517

[mcy]

Ralf: so my read of the LangRef seems inconsistent with yours. Looking at the definition of gep inbounds1:

The base pointer has an in bounds address of an allocated object, which means that it points into an allocated object, or to its end. The only in bounds address for a null pointer in the default address-space is the null pointer itself.

My read of this is that the null pointer points to a zero-width allocation, so I'm pretty sure the LLVM snippet given is sound, and defined to be T* 0. As mentioned above, this mirrors the special case in the C++ standard (I can pull up the citation if you ask, I just don't wanna dive into the standard rn). I'm curious to see where the LLVM folks said otherwise, since that seems contrary to what I've seen them say.

In particular, Clang lowers p + 0 the same (gep inbounds) in C and C++; if LLVM had C semantics, the C++ lowering is unsound. https://godbolt.org/z/esjW1e7Md

So currently, Miri accepts (1 as *mut u8).add(0) because otherwise the standard library is horribly unsound

The funny thing is that we actually have the reverse of the C++ rules: 0x1 + 0 is disallowed, but 0x0 + 0 is defined to be 0x0. I agree that p + 0 := p for all pointers p regardless of value, liveness, provenance, or inferred volatility. This seems kind of hard without getting cooperation from LLVM.

For non-0 offsets, like in (1 as *mut u8).add(1), I think there is no question: this is definitely disallowed, since there would have to be an allocation of size at least 1 here to accept this. Only .add(0) is interesting.

Yup. I only mentioned it to make sure I wasn't crazy. It would not make sense to allow that.

In the meantime, can we document the current Miri behavior under <*mut T>::add? Zero offsets are really weird and confuse people in C, C++, and Rust alllll the time.

[mcy]

Ah, and let us not forget the classic companion to this question. Is the following program UB?

std::memcpy(nullptr, nullptr, 0);

All three languages say "yes". I believe Rust says no if the pointers are 0x1 or similar for the same reasons Ralf gives above.

[RalfJung]

My read of this is that the null pointer points to a zero-width allocation, so I'm pretty sure the LLVM snippet given is sound, and defined to be T* 0.

We seem to agree that .add(0) is sound if and only if at the given address there exists a zero-sized allocation.

But NULL is explicitly a pointer where no allocation can ever exist in LLVM. I would hence argue that there cannot exist a zero-sized allocation at NULL, either. Put differently: given that no allocation can exist at NULL, then if add(0) is valid on the NULL pointer, it should be valid on all pointers, even pointers to deallocated objects -- would you agree to that? To be concrete about the latter case, I mean code like this:

let ptr = Box::into_raw(Box::new(0i32));
drop(Box::from_raw(ptr));
ptr.add(0); // UB or not? Miri says UB.

I tried to ask the LLVM devs about this and here is part of the thread (it's stretched across several months so browsing the full thread is super annoying). It was hard for me to extract much concrete from this, but it seemed pretty clear that .add(0) can be invalid for some pointers. I hence made Miri as conservative as I could, making .add(0) invalid for as many pointers as possible without drowning the standard library in error messages. This is using Miri to explore possible specifications, not using Miri to document any prior decision -- there cannot be a decision since LLVM is a mess. :(

It seems you are saying that maybe NULL.add(0) is actually okay (it has to be for clang to be C++-compliant -- but that does not mean much, clang has been violating the C standard for a decade or so until they finally fixed their infinite loop optimizations) -- but possibly examples like the ones above could still be not okay, making dangling pointers "more invalid" than NULL? But that seems ridiculous and pointless. If NULL.add(0) is valid, an analysis can already deduce basically nothing from a GEPi with offset 0, and hence it seems to make no sense at all to forbid this for other pointers.

I was not aware of the NULL + 0 rule in C++. so it would be good to have a citation for this if you could dig that up. Maybe with that information in our hand, we can make another attempt at talking to the LLVM people and convince them that GEPi with offset 0 should just always be valid.

In the meantime, can we document the current Miri behavior under <*mut T>::add? Zero offsets are really weird and confuse people in C, C++, and Rust alllll the time.

Since the current Miri behavior is just whatever I put in the code to make the tests pass, I don't think we should make it normative by documenting it.

I think the only way to make progress on this issue is to get LLVM to improve their LangRef. Until we do that, everything Rust does is like building on quicksand. I tried and failed. Maybe someone else wants to give it a try? :D

std::memcpy(nullptr, nullptr, 0);

Maybe let's not open more than one Pandora's box per issue. ;)

[RalfJung]

Speaking of Pandora's boxes, the .add(0) issue is closely related to why our docs for pointer validity say some really surprising things about zero-sized accesses. :(

[comex]

I haven't looked at the thread yet, but looking at @mcy's quote:

The only in bounds address for a null pointer in the default address-space is the null pointer itself.

This implies that the null pointer is an "in bounds address" for a base of null; otherwise it would have said something like "There are no in bounds addresses for a null pointer in the default address-space." Since the only time the LangRef mentions "in bounds addresses" is with respect to getelementptr, unless I'm missing something, that directly implies that a getelementptr inbounds that takes null as the base address and returns null can be valid.

Of course, it's possible that the LangRef is just wrong. But as it's written, my take is that it does unambiguously permit NULL + 0.

[comex]

Looks like this language was added in:

commit 13f2e353110c3523295ed6026622d897f7506bbe
Author: Eli Friedman <efriedma@codeaurora.org>
Date:   Thu Feb 23 00:48:18 2017 +0000

    Explicitly state the behavior of inbounds with a null pointer.
    
    See https://llvm.org/bugs/show_bug.cgi?id=31439; this reflects LLVM's
    behavior in practice, and should be compatible with C/C++ rules.
    
    Differential Revision: https://reviews.llvm.org/D28026
    
    llvm-svn: 295916

The linked bug report is about NULL + 0, and Richard Smith mentions:

C++ allows null + 0, but not anything beyond that (as if there is a 0 element array at the null pointer).

So indeed, LLVM intentionally allows 'NULL + 0' in order to match C++, notwithstanding the strangeness you mentioned. I agree this would be a good reason to reopen the discussion about 'deallocated + 0'.

[Diggsey]

I haven't looked at the thread yet, but looking at @mcy's quote:

The thread doesn't cover the "base=NULL" case specifically - it's more about how an "allocation" is defined when it's not known to LLVM (ie. the base=0x1 case), My reading of that LangRef quote agrees that GEP inbounds NULL + 0 is not poison.

[RalfJung]

@comex I agree -- I must have missed or forgotten about that part of the LangRef.

However, on the Miri side, I think I'd like to maintain the symmetry that for ptr pointing to a zero-sized type, ptr.add(n) is allowed if and only if ptr.read() is allowed. Or, to put it differently, allowing null.add(0) would require putting in a special case for the NULL pointer, whereas right now Miri is treating NULL like any deallocated address, avoiding a special case.

[Diggsey]

So currently, Miri accepts (1 as *mut u8).add(0) because otherwise the standard library is horribly unsound, but rejects (0 as *mut u8).add(0)

to put it differently, allowing null.add(0) would require putting in a special case for the NULL pointer

Does this mean MIRI currently has a special-case for 0x1?