New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tracking issue for RFC 2043: Add `align_offset` intrinsic and `[T]::align_to` function #44488

Open
aturon opened this Issue Sep 11, 2017 · 24 comments

Comments

Projects
None yet
@aturon
Member

aturon commented Sep 11, 2017

This is a tracking issue for the RFC "Add align_offset intrinsic and [T]::align_to function " (rust-lang/rfcs#2043).

Steps:

Unresolved questions:

  • "produce a lint in case sizeof<T>() % sizeof<U>() != 0 and in case the expansion is not part of a monomorphisation, since in that case align_to is statically known to never be effective

frewsxcv added a commit to frewsxcv/rust that referenced this issue Sep 16, 2017

alexcrichton added a commit to alexcrichton/rust that referenced this issue Sep 16, 2017

alexcrichton added a commit to alexcrichton/rust that referenced this issue Sep 16, 2017

alexcrichton added a commit to alexcrichton/rust that referenced this issue Sep 18, 2017

alexcrichton added a commit to alexcrichton/rust that referenced this issue Sep 18, 2017

GuillaumeGomez added a commit to GuillaumeGomez/rust that referenced this issue Dec 18, 2017

Rollup merge of rust-lang#46812 - kennytm:fix-align-offset-sign, r=pe…
…trochenkov

Fix the wrong subtraction in align_offset intrinsic.

Given how the stage0 implementation in rust-lang#43903 is written, as well as that in the RFC, I suppose the current implementation has a typo.

cc rust-lang#44488, cc @oli-obk.
@SimonSapin

This comment has been minimized.

Contributor

SimonSapin commented Mar 17, 2018

@oli-obk Is it useful to stabilize align_offset before align_to is implemented?

@oli-obk

This comment has been minimized.

Contributor

oli-obk commented Mar 17, 2018

Generally yes, because that's the key feature. Align_to is just convenience

@SimonSapin

This comment has been minimized.

Contributor

SimonSapin commented Mar 17, 2018

Alright, then. Let’s stabilize align_offset and leave this issue open for tracking align_to.

@rfcbot fcp merge

@rfcbot

This comment has been minimized.

rfcbot commented Mar 17, 2018

Team member @SimonSapin has proposed to merge this. The next step is review by the rest of the tagged teams:

Concerns:

Once a majority of reviewers approve (and none object), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

@alexcrichton

This comment has been minimized.

Member

alexcrichton commented Mar 19, 2018

@rfcbot concern motivation-and-ergonomics

The original motivation for these functions (unless it's changed, which it may have!) I believe was for miri and const evaluating various functions. Is that still the main motivation for these functions? If so do we expect that more things to be available on stable once these are stabilized?

I'm a little unclear about how and when such an intrinsic would be used so I'm mostly looking to straighten up my own thinking! In particular the clause "If it is not possible to align the pointer, the implementation returns usize::max_value()." I'm having trouble wrapping my head around in how it'd be expected to get used.

Is the long term plan to make this a const fn but otherwise disallow operations like *mut T as usize in a const fn?

In terms of ergonomics I'd also naively expect a signature like:

pub fn align_to(self, align: usize) -> Option<*mut Self>;

but would that create the same problems it's trying to avoid?

@oli-obk

This comment has been minimized.

Contributor

oli-obk commented Mar 19, 2018

Is that still the main motivation for these functions?

yes

If so do we expect that more things to be available on stable once these are stabilized?

This will allow making it const fn, which is a separate topic in the future

I'm having trouble wrapping my head around in how it'd be expected to get used.

No matter which computation you use to figure out the number of bytes that you need to offset your pointer in order to make it aligned, you will need to check whether it still points into your buffer. If you have a [u8; 3] and have a pointer to the first element, how many bytes to do you need to offset in order to get a 8 byte aligned pointer? that might be beyond the range. So you always need to check. Returning max_value means that you can't align it in any buffer.

Is the long term plan to make this a const fn but otherwise disallow operations like *mut T as usize in a const fn?

No, these operations are fine. The issue is that no matter how many bytes you offset a *mut u8 in miri, it will never become aligned to anything with a higher alignment. This function exists to abstract away such manual pointer alignments.

In terms of ergonomics I'd also naively expect a signature like:

You could do that, but then you'd also need an argument for the allocation size. Now that I think about it, that doesn't seem too bad and since you need to check anyway... As long as the intrinsic doesn't have to return an Option (the intrinsic an impl detail anyway).

@alexcrichton

This comment has been minimized.

Member

alexcrichton commented Mar 19, 2018

Ok, thanks for the info! It sounds like this function doesn't necessarily unlock anything in the near term as const-things are still pretty unstable? If that's the case I'm personally tempted to leave these as unstable until we've got the const story more fleshed out to see how they fit into the grand scheme of things

@nagisa

This comment has been minimized.

Contributor

nagisa commented Mar 26, 2018

Oh dear, it has been almost a year since the RFC and it went totally outside my radar, until I really, really needed [T]::align_to for my current use case of… aligning a byte buffer :)

Thinking about possible implementation approaches, I realised that to implement [T]::align_to in some cases it would be necessary to resort to calling the intrinsic multiple times in a manner similar to this:

loop {
    x = intrinsics::align_offset(ptr, align);
    if (x is aligned to object start) { return }
    ptr = x.offset(1);
}

So with @oli-obk we decided that it would probably be most prudent to simply change the intrinsic to do such calculation by itself, changing its signature from the current one to align_offset<T>(*mut T, usize) -> *mut T, that aligns the pointer to the first aligned object, not the first aligned pointer value, like it does currently.

@nagisa

This comment has been minimized.

Contributor

nagisa commented Apr 28, 2018

I’m almost done with the improved implementation of the align_offset intrinsic, and I have noticed, that we currently specify that offset returned by the code is in bytes. This seems suboptimal in multiple ways.

  1. Since implementation works strictly in units of "elements", a conversion step is always necessary for when the stride of T does not equal 1;
  2. Furthermore, to implement align_to, conversion from bytes back to elements is necessary again;
  3. Cannot be used directly with ptr.offset()/ptr.offset_to without converting bytes back into "elements" again;

I propose that we change align_offset to return offset in number of elements.

@oli-obk

This comment has been minimized.

Contributor

oli-obk commented Apr 28, 2018

I'm assuming we are talking about elements of the source slice and not the aligned slice. Sgtm

@nagisa

This comment has been minimized.

Contributor

nagisa commented Apr 28, 2018

I guess I should’ve said in “number of Ts” where <*const T>::align_offset(...), but yeah.

@scottmcm

This comment has been minimized.

Member

scottmcm commented Apr 28, 2018

IIRC this was in bytes in the intrinsic because the pointer to align could have a ZST pointee, and always using bytes sidesteps the questions of what to do there. (Not that I'm sure why you'd want to align a *const [i32; 0] to *const [u64; 0], but you could.) The library could plausibly have a better API, though...

@nagisa

This comment has been minimized.

Contributor

nagisa commented Apr 30, 2018

FYI implementation for align_to and changes to align_offset are at #50319.

bors added a commit that referenced this issue May 17, 2018

Auto merge of #50319 - nagisa:align_to, r=alexcrichton
Implement [T]::align_to

Note that this PR deviates from what is accepted by RFC slightly by making `align_offset` to return an offset in elements, rather than bytes. This is necessary to sanely support `[T]::align_to` and also simply makes more sense™. The caveat is that trying to align a pointer of ZST is now an equivalent to `is_aligned` check, rather than anything else (as no number of ZST elements will align a misaligned ZST pointer).

It also implements the `align_to` slightly differently than proposed in the RFC to properly handle cases where size of T and U aren’t co-prime.

Furthermore, a promise is made that the slice containing `U`s will be as large as possible (contrary to the RFC) – otherwise the function is quite useless.

The implementation uses quite a few underhanded tricks and takes advantage of the fact that alignment is a power-of-two quite heavily to optimise the machine code down to something that results in as few known-expensive instructions as possible. Currently calling `ptr.align_offset` with an unknown-at-compile-time `align` results in code that has just a single "expensive" modulo operation; the rest is "cheap" arithmetic and bitwise ops.

cc #44488 @oli-obk

As mentioned in the commit message for align_offset, many thanks go to Chris McDonald.

bors added a commit that referenced this issue May 18, 2018

Auto merge of #50319 - nagisa:align_to, r=alexcrichton
Implement [T]::align_to

Note that this PR deviates from what is accepted by RFC slightly by making `align_offset` to return an offset in elements, rather than bytes. This is necessary to sanely support `[T]::align_to` and also simply makes more sense™. The caveat is that trying to align a pointer of ZST is now an equivalent to `is_aligned` check, rather than anything else (as no number of ZST elements will align a misaligned ZST pointer).

It also implements the `align_to` slightly differently than proposed in the RFC to properly handle cases where size of T and U aren’t co-prime.

Furthermore, a promise is made that the slice containing `U`s will be as large as possible (contrary to the RFC) – otherwise the function is quite useless.

The implementation uses quite a few underhanded tricks and takes advantage of the fact that alignment is a power-of-two quite heavily to optimise the machine code down to something that results in as few known-expensive instructions as possible. Currently calling `ptr.align_offset` with an unknown-at-compile-time `align` results in code that has just a single "expensive" modulo operation; the rest is "cheap" arithmetic and bitwise ops.

cc #44488 @oli-obk

As mentioned in the commit message for align_offset, many thanks go to Chris McDonald.

bors added a commit that referenced this issue May 18, 2018

Auto merge of #50319 - nagisa:align_to, r=alexcrichton
Implement [T]::align_to

Note that this PR deviates from what is accepted by RFC slightly by making `align_offset` to return an offset in elements, rather than bytes. This is necessary to sanely support `[T]::align_to` and also simply makes more sense™. The caveat is that trying to align a pointer of ZST is now an equivalent to `is_aligned` check, rather than anything else (as no number of ZST elements will align a misaligned ZST pointer).

It also implements the `align_to` slightly differently than proposed in the RFC to properly handle cases where size of T and U aren’t co-prime.

Furthermore, a promise is made that the slice containing `U`s will be as large as possible (contrary to the RFC) – otherwise the function is quite useless.

The implementation uses quite a few underhanded tricks and takes advantage of the fact that alignment is a power-of-two quite heavily to optimise the machine code down to something that results in as few known-expensive instructions as possible. Currently calling `ptr.align_offset` with an unknown-at-compile-time `align` results in code that has just a single "expensive" modulo operation; the rest is "cheap" arithmetic and bitwise ops.

cc #44488 @oli-obk

As mentioned in the commit message for align_offset, many thanks go to Chris McDonald.
@RalfJung

This comment has been minimized.

Member

RalfJung commented Aug 2, 2018

As another case in point that getting this code right when hand-written is hard: Spot the issue in this code.

The problem is that the inner slice is not aligned properly in all cases when it is empty.

If we had a stable align_to, they could just use that. :)

@oli-obk

This comment has been minimized.

Contributor

oli-obk commented Aug 2, 2018

ping @llogiq

@llogiq

This comment has been minimized.

Contributor

llogiq commented Aug 2, 2018

This shouldn't happen because we only call the function for larger slices. But I've been wrong in the past, so I wouldn't bet on it.

@nagisa

This comment has been minimized.

Contributor

nagisa commented Aug 26, 2018

I’d like to suggest to focus on stabilising [T]::align_to if we are not sure whether align_offset is a right API for us. [T]::align_to seems to me like something that has provably the ideal API for what it does and covers majority of the use cases of the bare-bones align_offset.

The fact that it took me (with a help from another person) months to implement align_to has something to say about non-triviality of such function.

@RalfJung

This comment has been minimized.

Member

RalfJung commented Aug 26, 2018

Agreed, the sooner we can get people to use this instead of hand-rolling their own, the better. :)

Just one comment on a remark in the implementation PR:

Furthermore, a promise is made that the slice containing Us will be as large as possible (contrary to the RFC) – otherwise the function is quite useless.

miri cannot guarantee this. So while the implementation should do that, users of this code should NOT rely on the U part being maximal.

I cannot think of a case where this is require for correctness anyway, is there one?

@nagisa

This comment has been minimized.

Contributor

nagisa commented Aug 26, 2018

Oh yes, that is true. I’m fine with removing that guarantee from the documentation.

@RalfJung

This comment has been minimized.

Member

RalfJung commented Aug 27, 2018

So, what would this take? Just open an RFC that stabilizes, and ask for FCP?

@scottmcm

This comment has been minimized.

Member

scottmcm commented Aug 28, 2018

@RalfJung Yeah, I think a PR to stabilize (with a comment about why) is sufficient.

@RalfJung

This comment has been minimized.

Member

RalfJung commented Aug 28, 2018

PR submitted: #53754

@SimonSapin

This comment has been minimized.

Contributor

SimonSapin commented Nov 4, 2018

<*mut u8>::align_offset can be useful when implementing a memory allocator, to satisfy the requested layout.align(). Note however that much of the complexity of the implementation of <*mut T>::align_offset does not apply when size_of::<T>() == 1. The function is also infallible in that case.

@alexcrichton Would a separate function or method for this special case (or maybe even for usize instead of pointers) address your concern?

@alexcrichton

This comment has been minimized.

Member

alexcrichton commented Nov 5, 2018

@SimonSapin yeah the API I mentioned above I think would be fine to add and consider stabilizing

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment