Hazards on uint overflow in std::vec

[bluss]

std::vec does not check for overflow properly, and it should be possible to crash Rust where uint overflow can be triggered in reserve logic (at least in 32-bit Rust).

• .reserve(n) must allocate n elements, or fail!() (or controlled OOM abort in the runtime/allocator); I think this is ok today.
• .reserve_at_least(n) must allocate at least n elements or fail!(). This is buggy today since sufficiently large n will round "up" to 0.
• Must check for overflow when computing new input to .reserve or .reverse_at_least
• Instances where we have possibility of overflow, then call to reserve method, then follows unsafe code assuming successful allocation:
  • https://github.com/mozilla/rust/blob/2690b513506dad53d0b86b20f8b73bc420dfb3a2/src/libstd/vec.rs#L1349
  • https://github.com/mozilla/rust/blob/2690b513506dad53d0b86b20f8b73bc420dfb3a2/src/libstd/vec.rs#L1358
  • https://github.com/mozilla/rust/blob/2690b513506dad53d0b86b20f8b73bc420dfb3a2/src/libstd/vec.rs#L1403
• Knock-off instances of the same problem in str
  • https://github.com/mozilla/rust/blob/2690b513506dad53d0b86b20f8b73bc420dfb3a2/src/libstd/str.rs#L156
  • https://github.com/mozilla/rust/blob/2690b513506dad53d0b86b20f8b73bc420dfb3a2/src/libstd/str.rs#L186
  • https://github.com/mozilla/rust/blob/2690b513506dad53d0b86b20f8b73bc420dfb3a2/src/libstd/str.rs#L1021
  • https://github.com/mozilla/rust/blob/2690b513506dad53d0b86b20f8b73bc420dfb3a2/src/libstd/str.rs#L2127
  • https://github.com/mozilla/rust/blob/2690b513506dad53d0b86b20f8b73bc420dfb3a2/src/libstd/str.rs#L2145
  • https://github.com/mozilla/rust/blob/2690b513506dad53d0b86b20f8b73bc420dfb3a2/src/libstd/str.rs#L2162

verdict: if you unsafe {}, check for overflow.

[huonw]

It seems these can/should be solved by using checked_add and checked_mul as a (almost) drop-in replacement for + and *.

[bluss]

I think we should add helper methods for "reserve space for N more elements". That way we solve this problem for user code too (is it needed?)

fn reserve_space_for_more(&mut self, more: uint) {  // find me a better name and write me less silly
    let newcap = self.len().checked_add(&more).expect("reserve_space_for_more: Overflow");
    self.reserve(cmp::max(newcap, uint::next_power_of_two(newcap))
}

[bluss]

• at_vec has overflow problems in its raw::reserve_raw too
• possibly rt::io::extensions::push_bytes

[thestinger]

Life would be easier if vectors were { length, capacity, *data }. It would also remove the need for OptVec.