slice-deque: `SliceDeque::with_capacity` and `SliceDeque::reserve` silently return insufficient capacity for huge capacities in release mode due to integer overflow

[kaixinlalala]

Description:

I have used afl.rs to fuzz the public APIs of this crate. While investigating crashes around SliceDeque::with_capacity and SliceDeque::reserve , I found that the function can behave incorrectly in release mode for very large capacity values.

The documentation says that with_capacity(n) creates an empty deque with capacity to hold n elements. Similarly, reserve(additional) should reserve capacity for at least additional more elements. However, for very large values, internal arithmetic such as 2 * n or 2 * new_capacity can overflow usize. In debug mode this causes an overflow panic, but in release mode the multiplication wraps around. This can make the function return successfully even though the resulting capacity is far smaller than requested.

Environment:

slice-deque version: 0.3.0

rustc version: 1.94.1

OS: Ubuntu 20.04.6 LTS

Reproduction code:

extern crate slice_deque;

fn main() {
    let requested = usize::MAX / 2 + 1;
    let d = slice_deque::SliceDeque::<u8>::with_capacity(requested);

    println!("requested capacity = {}", requested);
    println!("actual capacity    = {}", d.capacity());
}

extern crate slice_deque;
fn main() {
    let requested = usize::MAX / 2 + 1;
    let mut d = slice_deque::SliceDeque::<u8>::new();
    d.reserve(requested);
    
    println!("requested capacity = {}", requested);
    println!("actual capacity    = {}", d.capacity());

}

I also placed the replay files at replay_files.

Expected behavior:

For with_capacity(n), if the function returns successfully, the returned deque should have capacity at least n.

For reserve(additional), if the function returns successfully, the deque should have capacity for at least additional more elements.

For these huge values, I would expect a capacity overflow panic or allocation failure. The functions should not successfully return a deque with a much smaller capacity than requested.

Actual behavior

In debug mode, the program panics due to integer overflow:

thread 'main' panicked at /Rust-Lib-Testing/test/tests/crates/slice-deque-0.3.0/src/lib.rs:410:45:
attempt to multiply with overflow
stack backtrace:
   0:     0x559cebcc5be8 - <std::sys::backtrace::BacktraceLock::print::DisplayBacktrace as core::fmt::Display>::fmt::h0f9d2e8e73f1bc7d
   1:     0x559cebd019f3 - core::fmt::write::h2b15537d64ec9505
   2:     0x559cebceeb9f - std::io::Write::write_fmt::h7f766131a16fe05a
   3:     0x559cebcc5a33 - std::sys::backtrace::BacktraceLock::print::h5e38585c963961db
   4:     0x559cebcc07bc - std::panicking::default_hook::{{closure}}::h7a475a2b7b7e4121
   5:     0x559cebcc065d - std::panicking::default_hook::hac0f4b95d0cecbc2
   6:     0x559cebcc0c91 - std::panicking::rust_panic_with_hook::hb51ba0f67890aa28
   7:     0x559cebcc5f96 - std::panicking::begin_panic_handler::{{closure}}::h73d0277a9a02463b
   8:     0x559cebcc5e09 - std::sys::backtrace::__rust_end_short_backtrace::hf93dae6c307b4fe8
   9:     0x559cebcc08ad - __rustc[b6f6af4e11d2f413]::rust_begin_unwind
  10:     0x559cebd00960 - core::panicking::panic_fmt::h3075732948299e49
  11:     0x559cebd008b7 - core::panicking::panic_const::panic_const_mul_overflow::hba844719457e0e77
  12:     0x559cebcbd8ec - slice_deque::SliceDeque<T>::with_capacity::h8dc3d5179c25f586
                               at /Rust-Lib-Testing/test/tests/crates/slice-deque-0.3.0/src/lib.rs:410:45
  13:     0x559cebcbcd4f - replay_slice_deque1::main::h2abf81457f189292
                               at /Rust-Lib-Testing/test/tests/crates/slice-deque-0.3.0/fuzz_target/slice_deque_importance_fuzz/multipleTargets/replay_slice_deque1/src/main.rs:6:13
  14:     0x559cebcbcb4b - core::ops::function::FnOnce::call_once::h127d8f7ae5af77f8
                               at /Rust-Lib-Testing/test/src/rust/library/core/src/ops/function.rs:253:5
  15:     0x559cebcbdbfe - std::sys::backtrace::__rust_begin_short_backtrace::h09b6bd66fc288ce6
                               at /Rust-Lib-Testing/test/src/rust/library/std/src/sys/backtrace.rs:158:18
  16:     0x559cebcbdbd1 - std::rt::lang_start::{{closure}}::h82f416d938689675
                               at /Rust-Lib-Testing/test/src/rust/library/std/src/rt.rs:206:18
  17:     0x559cebced885 - std::rt::lang_start_internal::h9de2b5630c7cec4d
  18:     0x559cebcbdbb7 - std::rt::lang_start::h01ad6e2ad60a32fa
                               at /Rust-Lib-Testing/test/src/rust/library/std/src/rt.rs:205:5
  19:     0x559cebcbce6e - main
  20:     0x7f24b12a6083 - __libc_start_main
                               at /build/glibc-B3wQXB/glibc-2.31/csu/../csu/libc-start.c:308:16
  21:     0x559cebcbc4fe - _start
  22:                0x0 - <unknown>

In release mode, the function succeeds but returns a deque with capacity 0:

requested capacity = 9223372036854775808
actual capacity    = 0

Similarly, reserve can return successfully without reserving the requested capacity.

Root cause:

The issue appears to be caused by unchecked multiplication in SliceDeque::with_capacity:

pub fn with_capacity(n: usize) -> Self {
    unsafe {
        let buf = Buffer::uninitialized(2 * n).unwrap_or_else(|e| {
            let s = tiny_str!(
                "failed to allocate a buffer with capacity \"{}\" due to \"{:?}\"",
                n, e
            );
            panic!("{}", s.as_str())
        });
        Self {
            elems_: nonnull_raw_slice(buf.ptr(), 0),
            buf,
        }
    }
}

SliceDeque::reserve eventually calls reserve_capacity, which also performs unchecked multiplication:

fn reserve_capacity(
    &mut self, new_capacity: usize,
) -> Result<(), AllocError> {
    unsafe {
        if new_capacity <= self.capacity() {
            return Ok(());
        }

        let mut new_buffer = Buffer::uninitialized(2 * new_capacity)?;
        debug_assert!(new_buffer.len() >= 2 * new_capacity);

        ...
    }
}

For n = usize::MAX / 2 + 1 , the expression: 2 * n , overflows usize.

In debug mode this causes a panic, but in release mode it wraps around to 0. As a result, the code effectively calls: Buffer::uninitialized(0), and returns a deque with capacity 0.

This issue affects values in the range: [usize::MAX / 2 + 1 , usize::MAX]

Possible fix:

Use checked arithmetic before allocating, for example:

let doubled = n.checked_mul(2).expect("capacity overflow");
let buf = Buffer::uninitialized(doubled).unwrap_or_else(|e| {
    ...
});

and similarly in reserve_capacity:

let doubled = new_capacity.checked_mul(2).ok_or(AllocError::Oom)?;
let mut new_buffer = Buffer::uninitialized(doubled)?;

I hope you can check whether this is a real bug that needs to be fixed. Thanks a lot.