LocalVector can crash with very large sizes

dhoverml commented 2 months ago

Tested versions

master (b75f0485ba15951b87f1d9a2d8dd0fcd55e178e4)

System information

Ubuntu 20.04 LTS

Issue description

Allocating a LocalVector with size > 0x80000000, with a non-trivially-constructible type, crashes.
Allocating a LocalVector with size > 0x80000000, with a trivially-constructible type, silently does not crash when indexed despite capacity == 0.

One potential fix is to change the code here: https://github.com/godotengine/godot/blob/master/core/templates/local_vector.h#L159-L163

From:

if (unlikely(p_size > capacity)) {
  capacity = tight ? p_size : nearest_power_of_2_templated(p_size);
  data = (T *)memrealloc(data, capacity * sizeof(T));
  CRASH_COND_MSG(!data, "Out of memory");
}

To:

if (unlikely(p_size > capacity)) {
  if (tight) {
    capacity = p_size;
  } else {
    // equivalent:
    //   capacity = max(nearest_power_of_2_templated(p_size), p_size)
    // or since this almost always doesn't happen
    //   U nearest = nearest_power_of_2_templated(p_size);
    //   if (unlikely(nearest < p_size)) {                 
    //     capacity = p_size;
    //   } else {
    //     capacity = nearest;
    //   }
    U nearest = nearest_power_of_2_templated(p_size);
    capacity = nearest < p_size ? p_size : nearest;
  }
  data = (T *)memrealloc(data, capacity * sizeof(T));
  CRASH_COND_MSG(!data, "Out of memory");
}

This will need to be done in other functions in LocalVector, as well as look over other places that use nearest_power_of_2_templated (and similar functions) in case they don't handle zero.

Steps to reproduce

Add this somewhere that is guaranteed to be executed when launching the app/editor:

LocalVector<Callable> vec;
vec.resize(0x80000001);

Compile and run:

# I added dev_build=yes in hopes of a more detailed stack trace.  It can be removed.
scons -j $(nproc) dev_build=yes target=editor optimize=debug && ./bin/godot.linuxbsd.editor.dev.x86_64

Output:

================================================================                                                                                                                                             
free(): invalid pointer                                                                               
Aborted (core dumped)

Trivially constructible types can result in undefined behavior or crash:

LocalVector<int> vec;
vec.resize(0x80000001);
print_line("size", vec.size(), "capacity", vec.get_capacity());
fflush(stdout);

// this usually doesn't crash, though it is undefined
print_line("vec[0]", vec[0]);
fflush(stdout);

// segmentation fault, usually
print_line("this usually crashes, but not this time", vec[0x80000000]);

Output

size 2147483649 capacity 0
vec[0] -671903936
Segmentation fault (core dumped)

Minimal reproduction project (MRP)

N/A

huwpascoe commented 2 months ago

If this can happen in multiple places throughout the codebase then it'd be good to have a formal definition of the resizing algorithm:

template<size_t ElementSize, size_t UpperLimit, bool PreferPow2, class OtherArgs...>
constexpr size_t calculate_new_capacity(size_t p_current_size, size_t p_new_size);

Something like that, anyway.

AThousandShips commented 2 months ago

It's not necessarily possible as different containers use different methods for memory management

godotengine / godot