[BUG]: UB in `cuda::shuffle_iterator` due to incorrect use of `bit_ceil`

[leofang]

Is this a duplicate?

• I confirmed there appear to be no duplicate issues for this bug and that I agree to the Code of Conduct

Type of Bug

Runtime Error

Component

libcu++

Describe the bug

bit_ceil causes overflow in the bit shifts below. The original PR (#4564) calls a custom get_cipher_bits which is an optimized version of bit_width.

Originally posted by @leofang in #5530 (comment)

How to Reproduce

Pass 100,000,000 as __num_elements to the constructor to see this.

cccl/libcudacxx/include/cuda/__random/feistel_bijection.h

Lines 58 to 64 in 8136b82

	_CCCL_API __feistel_bijection(uint64_t __num_elements, _RNG&& __gen)
	{
	const uint64_t __total_bits = (::cuda::std::max) (uint64_t{4}, ::cuda::std::bit_ceil(__num_elements));
	// Half bits rounded down
	__left_side_bits = __total_bits / 2;
	__left_side_mask = (1ull << __left_side_bits) - 1;

Expected behavior

The original PR before porting (#4564) was correct.

Reproduction link

No response

Operating System

No response

nvidia-smi output

No response

NVCC version

No response

[fbusato]

taking a look

[fbusato]

@leofang, this doesn't look a bug but the usage of the wrong function. bit_ceil returns the "next power-of-two", not the number of bits. see https://en.cppreference.com/w/cpp/numeric/bit_ceil.html.

bit_ceil(100'000'00) correctly returns 134'217'728 https://godbolt.org/z/xcMG5s7Po

[leofang]

Please pass 100,000,000 to shuffle_iterators to see what I meant.

[leofang]

bit_ceil(100'000'00) correctly returns 134'217'728 https://godbolt.org/z/xcMG5s7Po

For example, please consider this line

const uint64_t __total_bits = (::cuda::std::max) (uint64_t{4}, ::cuda::std::bit_ceil(__num_elements)); 

You would get __total_bits = 134'217'728.

[fbusato]

yes, this is the expected result for bit_ceil

[fbusato]

Please pass 100,000,000 to shuffle_iterators to see what I meant.

ok, got it. In this case, the bug is in shuffle_iterators not in bit_ceil

[fbusato]

@miscco what was the original intention of the code? probably, just bit_width