`align_offset` infinite loop

[lukas-code]

I tried this code: (Playground)

fn main() {
    struct HugeSize([u8; (1 << 47) - 1]);
    let _ = ((1usize << 47) as *const HugeSize).align_offset(1 << 47);
}

I expected to see this happen: The program terminates.

Instead, this happened: The program loops indefinitely.

I encountered this while working on #102795

Meta

rustc --version --verbose:

rustc 1.66.0-nightly (dcb376115 2022-10-20)
binary: rustc
commit-hash: dcb376115066d111dbf5f13d5ac2a2dbe8c12add
commit-date: 2022-10-20
host: x86_64-unknown-linux-gnu
release: 1.66.0-nightly
LLVM version: 15.0.2

[lukas-code]

Hangs here:

rust/library/core/src/ptr/mod.rs

Lines 1637 to 1649 in cc9b259

	loop {
	// y = y * (2 - xy) mod n
	//
	// Note, that we use wrapping operations here intentionally – the original formula
	// uses e.g., subtraction `mod n`. It is entirely fine to do them `mod
	// usize::MAX` instead, because we take the result `mod n` at the end
	// anyway.
	inverse = wrapping_mul(inverse, wrapping_sub(2usize, wrapping_mul(x, inverse)));
	if going_mod >= m {
	return inverse & m_minus_one;
	}
	going_mod = wrapping_mul(going_mod, going_mod);
	}

@rustbot label I-hang

[thomcc]

CC @nagisa

[nagisa]

Thanks for the report.

Priority wise, this seems like it isn’t going to be super high priority to resolve, given that 1<<47 is 128TiB. 128TiB, unfortunately, is half of the maximum supported address space on many modern x86_64 and aarch64 deployments, so it is conceivable that this could be actually hit. Still would be nice to actually fix it.

As for the strategies to fix this, there are a couple of approaches to consider:

1. We could store the going_mod into a u128 (2 * usize on any supported platform today.)

• This is not super future-proof, and unfortunately probably somewhat more costly in the non-const-evaluated case.

2. We could use saturating_mul instead of wrapping_mul. When going_mod overflows on the last iteration, it will become the maximum value that fits in usize and the termination condition will be hit.

• Not super clear what codegen quality implications are for using saturating_mul;

3. Compute a widening/checked multiplication and additionally compare the high bits for != 0 in the terminating condition.

• This is an alteration of 1. I suspect this is going to produce the best code, but that remains to be seen.

[jruderman]

Would it work to change the termination condition from going_mod >= m to going_mod >= m || going_mod == 0? Where going_mod == 0 means it wrapped, so the logical value is out of the type's range, and thus bigger than m.

[jruderman]

Or weirder: store log_2_going_mod instead of going_mod, so the comparison can be done using ctlz(m) and the squaring operation can be replaced with a doubling (bit shift).