add an is_aligned intrinsic to rust

[oli-obk]

This intrinsic takes a raw pointer and an alignment and checks whether the pointer is aligned wrt the given alignment. Implementations like miri can use this to always return false, if the requested alignment is bigger than the alignment given at creation of the allocation that the pointer points into.

In the future platforms which don't require alignment can return true unconditionally, which will probably allow more optimizations to trigger on those platforms.

The signature of the intrinsic can either be fn<T>(* const T, usize) or just fn<T>(* const T) where the latter obtains the alignment to be checked from the pointee type.

Most platforms should simply generate (ptr as usize) & ((1 << (align - 1) - 1) == 0

An example of such a check in the stdlib is

rust/src/libcore/str/mod.rs

Line 1433 in f09576c

let align = (ptr as usize + index) & (usize_bytes - 1);

which is part of utf8 checking. Without such an intrinsic, miri can never do utf8 checking.

Does a change like this require an rfc?

[eddyb]

cc @rust-lang/compiler

[joshlf]

@oli-obk

In the future platforms which don't require alignment can return true unconditionally, which will probably allow more optimizations to trigger on those platforms.

To clarify, the function's behavior isn't "is this address a multiple of this alignment," but rather "is this address a multiple of this alignment OR does the current platform not require alignments"?

[oli-obk]

Well... it's stating whether the pointer is aligned. The platform might say it is aligned. So we should probably use the second signature. The one without an align argument. You can always err on the safe side in the impl, there's no guarantee this function will ever return true after returning false on a pointer. No matter what you do to the pointer.

[joshlf]

@oli-obk

The reason I'm confused is that Rust has two different notions of alignment. One, described here in the Rustonomicon, is a purely Rust concept, and used only for allocation. E.g., stack- and heap-allocated values of a type, T, should have the alignment core::mem::align_of::<T>().

The other concept is the architecture's notion of alignment. This is just the alignment that is required in order for a data access to be correct (e.g., some processors are incapable of loading an 8-byte word into a register if that word is not 8-byte aligned, and on some processors, it will work but will be quite slow), and I suspect is the kind of alignment that you're referring to.

Note that there's certainly a relationship between the two. Namely, the Rust compiler will make a decision about Rust alignment that takes the processor's alignment requirements into consideration. But the Rust notion of alignment is also more powerful than that. For example, there's a proposal right now to allow the user to specify that a type has a particular alignment that is greater than the alignment that Rust would normally assign it. This is useful for, e.g., ensuring that a value will fit in a single cache line and will not be allocated to straddle two cache lines.

Thus, I suspect that what you're asking for isn't "is this *mut T aligned according to core::mem::align_of::<T>()", but rather, "is this *mut T aligned according to this processor's alignment requirements?" Is that accurate?

[oli-obk]

We can leave out the processor part, if adding an arbitrary integer to an address is allowed to still return false, even if the generic pointer arithmetic would allow it on all major platforms.

In miri the intrinsic would answer the question: is the pointer pointing into an allocation that was created with the alignment or a bigger one and is the pointer offset within that allocation by a multiple of the alignment.

[joshlf]

OK so you're concerned in particular with the Rust definition of alignment? In other words, the following would be a valid implementation?

fn is_aligned<T>(ptr: *mut T) -> bool {
    use core::mem::align_of;
    (ptr as usize) % align_of::<T>() == 0
}

[joshlf]

Also, why does this need to be an intrinsic and not a function? I'll admit that I'm not terribly familiar with miri or MIR, so I'm not sure that I quite understand your use case.

[eddyb]

On second thought, "will an aligned memory access succeed" is much better and shouldn't be misusable.

[joshlf]

@eddyb can you elaborate? I assume you mean, "given an alignment, a, is it guaranteed that a memory access with at least alignment a will succeed?"

[eddyb]

Yes. The miri situation is trickier to explain but basically all allocations are independent and have no base address that you can observe, and together with byte offsets they form abstract pointers, for which all pointer operations work but not trying to manipulate the pointer as an integer.

To make matters worse, even if miri did some kind of symbolic execution to handle code that poked at some bits of pointers, it would have to interpret all codepaths, both the unaligned and the optimized aligned ones, because the pointer could, at runtime, have an arbitrary alignment.

This isn't just a theoretical problem, if miri starts being used for evaluating static data (as is the plan), then a pointer in miri would have a corresponding runtime address that miri would be wrong to assume anything about.

[joshlf]

Gotcha. And the reason that this ought to be an intrinsic is that the question "does the alignment a guarantee success" is really a processor achitecture-dependent one? E.g., the answer might always be "yes" on x86, but could be "no" (depending on a) on ARM?

[eddyb]

Ah that is because the backend handles itrinsics: so LLVM could do one thing and miri do another.

[nikomatsakis]

Can someone clarify why miri cannot do alignment checking? Is it because it requires converting pointers into addresses and allowing bit manipulation and so forth?

[nikomatsakis]

Also, when we say miri, I think what we really mean is "constant evaluation (done with miri)", right?

[eddyb]

Some bit manipulations could be soundly supported. The trouble is with trying to align an offset within an allocation with alignment of 1 (or anything lower than the desired alignment).
The result is not expressible as a constant offset because the actual address can be anything.

[oli-obk]

Miri does alignment checking. The issue is that when you allocate an 1 byte aligned array, how many bytes do you need to offset the pointer so the pointer is guaranteed to be 8 byte aligned? This is unanswerable in a deterministic manner, because you need to know the position of the first byte, which you never know before you run the program. So running a program twice might yield different results, because the initial offset might change. For constant evaluation this is not acceptable.

[nikomatsakis]

Personally, I think that this should go through an RFC -- this is because it seems like something we would want to expose publicly, so that other libraries and implementors can build on it, and it seems good to get the design right.

[oli-obk]

That makes sense. I'll open an RFC.

[nikomatsakis]

I'm going to close this issue in the meantime then, ok @oli-obk ? (If you'd rather keep it open, feel free to re-open.)