LLVM semantics vs mmap/munmap

Alive accepts the following transformation:

define i32 @src() {
  %mem = call ptr @mymmap()
  %ptr1 = gep inbounds ptr %mem, 1 x i64 6000
  %val1 = load i8, ptr %ptr1, align 1
  call void @mymunmap(noundef ptr %mem)
  %1 = load i8, ptr %mem, align 1
  ret i32 0
define i32 @tgt() {
  %mem = call ptr @mymmap()
  %ptr1 = gep inbounds ptr %mem, 1 x i64 6000
  %val1 = load i8, ptr %ptr1, align 1
  call void @mymunmap(noundef ptr %mem)
  %ptr2 = gep inbounds ptr %mem, 1 x i64 6000
  %val2 = load i8, ptr %ptr2, align 1
  ret i32 0
Transformation seems to be correct!

This is somewhat concerning, as it indicates that the following would be UB:

  • use mmap to allocate a large range of pages (in mymmap)
  • access them as a single big allocation
  • use munmap to remove the 2nd half of pages (in mymunmap)
  • access the first half of pages using the same pointers as before

The man page for munmap doesn’t give any indication that there would be a problem here, so this seems like a completely reasonable programming pattern to me. And yet, if what Alive says is correct, then the original code has UB in LLVM. I can’t find any documentation about mmap, clang, the C standard, or the LLVM LangRef that would alert programmers of this UB. Is Alive wrong here or is this truly UB?

I have been told before that LLVM assumes that allocations cannot shrink, and I can see how it could make that assumption about malloced allocations since it “controls” the allocator there, but in this example there is no malloc that LLVM can see. I was pointed to this part of the Zig allocator API which lets allocations grow/shrink in-place; that seems to me like another example of code that LLVM might miscompile if it assumes that no accessible memory region (no matter how it was created) can ever shrink.

(I’ve asked about mmap before, but that was about nastier cases like memory regions with gaps. I didn’t quite expect even these seemingly simpler cases to be problematic.)

LangRef is written to assume that memory is allocated, lives for a certain amount of time, then is deallocated.

But as a practical matter, this mostly only matters for allocations where LLVM knows the size in the first place, i.e. malloc, and other functions marked with allocation attributes. If the allocation is opaque to LLVM, LLVM doesn’t know what offsets are valid in the first place, so it doesn’t really matter if the size changes.

We should be able to adjust LangRef to make your testcase well-defined without any practical impact, I think.

Doesn’t this example have the same issues with provenance as the mmap with gaps? I.e. wouldn’t unmap be technically producing a new provenance so using the old pointer (without integer cast dance) would be incorrect?

From a previous question on Alive2’s GitHub, https://github.com/AliveToolkit/alive2/issues/934 strongly implies to us that allocations cannot shrink in the model, which seems incompatible with the concept of partial munmap period. (Indeed, there’s no way for a programmer to “refresh” the pointer without integer cast dances, as munmap doesn’t return a pointer). I assume removing these assumptions are non-trivial, but is this doable in a few months kind of nontrivial, or rewrite from scratch a majority of LLVM transforms non-trivial?

I guess the question is whether any LLVM passes actually do the kind of analysis that Alive allows in the example.

IOW, is this a change that only affects LangRef and Alive, or does it need code changes?

Pretty sure that LLVM can just remove those loads since their results are unused, and if you add uses, then this transformation is no longer correct.

The question is whether LLVM is allowed to introduce spurious loads after myunmap. The example is obviously artificial; it just demonstrates that Alive is okay with a spurious load.

Concretely, under the following conditions:

  • if some pointer was dereferenceable for N bytes before a call (which we can know e.g. because a load happened)
  • and then we call some function we cannot analyze
  • and then the pointer is witnessed to be dereferenceable for at least 1 byte (e.g. because there is another load)

is LLVM allowed to now deduce that the pointer is still dereferenceable for N bytes? The Alive example seems to indicate that the answer is “yes”, but that would be a problem for partial munmap, as described above.

I don’t know if LLVM currently has any optimizations that would violate this (by propagating dereferenceable info across an unknown call), but ISTM that ought to only be permitted with the ‘nofree’ attribute (munmap doesn’t free the whole pointer, but it does free part of it).

I think it’s more like

  • Some pointer is dereferenceable at offset1
  • and then we call some function we cannot analyze
  • and then the pointer is witnessed to be dereferenceable at offest2 (== 0 in the example)

The LLVM can deduce that the pointer is dereferenceable in [min(offset1, offset2), max(offset1, offset2)] after the call.
Don’t know if any current pass takes advantage of that, but it seems in line with the proposed memory model. Alternatively, we’d need to drop dereferenceability assumptions (even provided by explicit attributes) on any unanalyzable (practically any) call. Which might not be so bad, if it’s the only thing required to support region shrinking, but here might be more.
I.e. making the object’s /allocation “size” not its intrinsic property tied to the provenance/whatever.

It would also make hoisting/sinking across most of the calls illegal.

Note that argument-level dereferenceable attributes in LLVM have a very strong semantics an assert that the pointer remains dereferenceable for the entire function call. So those don’t have to be dropped on opaque calls.

The langref doesn’t seem to actually explicitly state that the dereferenceable property must be preserved throughout the entire execution of the body. Is that actually true (versus applying only at the time of the call)? If so, it would be good to clarify the wording there.

Also…since the dereferenceable attr is used for C++ reference types in Clang…is that strong semantic even correct for C++ references? A C++ ref must refer to a valid object at the point of creation, but AFAIK the object referred to is not required to outlive the reference.

For example, is this C++ code actually UB if x and y point to the same object? We mark x dereferenceable(4) in the IR, but in that situation, it is not dereferenceable during the entire body.

int foo(int &x, int *y) {
    int ret = x;
    return ret;

Oh, that’s apparently already known and been discussed, but not yet resolved.

see previous discussion in RFC: Decomposing deref(N) into deref(N) + nofree @preames

edit: ninja’d :slight_smile:

Yes, I definitely agree that if partial deallocation is a thing, then nofree should mean “no partial or complete deallocation”.

The question is whether LLVM is permitted to do reasoning of that sort without any attribute about the function called in the middle.