Game crashes on range(0,100000000)

[AlexHolly]

I get a Game crash on range(0,100000000) and no error messages.

[akien-mga]

Steps to reproduce? Is that a regression or did you just happen to try iterating over 100 million elements, which is likely not possible with single float precision?

[vnen]

It does give a segfault with a for i in range(0,100000000) and also with a var temp = range(0,100000000). Likely due to precision indeed, but segfaults are never good. At least the debugger should catch this IMO.

[neikeq]

I agree with @vnen. Debugger should catch this.

[akien-mga]

Yeah I did not mean that it shouldn't be fixed, only that a oneliner bug report is always a bit too short :)

[akien-mga]

Maybe VALIDATE_ARG_NUM should catch integer overflows?

godot/modules/gdscript/gd_functions.cpp

Lines 131 to 139 in 7af864f

	#define VALIDATE_ARG_NUM(m_arg) \
	if (!p_args[m_arg]->is_num()) {\
	r_error.error=Variant::CallError::CALL_ERROR_INVALID_ARGUMENT;\
	r_error.argument=m_arg;\
	r_error.expected=Variant::REAL;\
	return;\
	}
	#else

[sheepandshepherd]

It looks like GDScript's range just allocates an array with ints in it (at least, it does when assigning the range to a variable -- the old wiki actually says it doesn't allocate). A value of 100 million fits just fine in a 32-bit int, but allocating a huge 100mil-length array might be causing the crash (that'd be 400MB in an IntArray, even more in a regular Array).

I also tested using a while loop that goes up to 100 million, and that doesn't crash.

[est31]

Yeah, it should really be worth a look to optimize for loops with range() to a while loop.

@akien-mga single precision floats have 23 bits in their fraction part. That means everything up to 2^32 - 1 should be fine, including 100 million.

I've reproduced the bug on commit 6a25a64 with gdb, and got this backtrace:

(gdb) bt
#0  0x0000000000410d32 in Variant::Variant (this=0x260c008) at core/variant.h:437
#1  0x0000000000447dc7 in Vector<Variant>::resize (this=0x2594ad8, p_size=100000000) at core/vector.h:282
#2  0x0000000001461ad7 in Array::resize (this=0x7fffffffc780, p_new_size=100000000) at core/array.cpp:140
#3  0x000000000049de4d in GDFunctions::call (p_func=GDFunctions::GEN_RANGE, p_args=0x7fffffffc930, p_arg_count=2, r_ret=..., r_error=...)
    at modules/gdscript/gd_functions.cpp:741
#4  0x0000000000476237 in GDFunction::call (this=0x25eacf8, p_instance=0x20a3150, p_args=0x0, p_argcount=0, r_err=..., p_state=0x0)
    at modules/gdscript/gd_script.cpp:731
#5  0x000000000047b146 in GDScript::_create_instance (this=0x25e8740, p_args=0x0, p_argcount=0, p_owner=0x25eaff0, p_isref=false, r_error=...)
    at modules/gdscript/gd_script.cpp:1466
#6  0x000000000047bba2 in GDScript::instance_create (this=0x25e8740, p_this=0x25eaff0) at modules/gdscript/gd_script.cpp:1660
#7  0x0000000001481409 in Object::set_script (this=0x25eaff0, p_script=...) at core/object.cpp:950
#8  0x000000000157dec4 in MainLoop::init (this=0x25eaff0) at core/os/main_loop.cpp:90
#9  0x0000000000c1f0fb in SceneTree::init (this=0x25eaff0) at scene/main/scene_main_loop.cpp:479
#10 0x0000000000404e86 in OS_Server::run (this=0x7fffffffdc90) at platform/server/os_server.cpp:225
#11 0x0000000000403e75 in main (argc=3, argv=0x7fffffffdee8) at platform/server/godot_server.cpp:41

So it crashes in Vector<T>::resize, confirming @sheepandshepherd 's theory. What's funny about this bug is that it doesn't crash in the actual code that's supposed to catch memory allocation errors, core/vector.h:273 , but in later code on line 282, calling memnew_placement.

[est31]

I found the problem. Vector<T>::resize (with T=Variant) does at vector.h line 263 the call _get_alloc_size(p_size).

Let's look at the definition of _get_alloc_size:

_FORCE_INLINE_ int _get_alloc_size(int p_elements) const {
    return  nearest_power_of_2(p_elements*sizeof(T)+sizeof(SafeRefCount)+sizeof(int));
}

So, it does a multiplication p_elements*sizeof(T). In our case, p_elements is 100 000 000, and sizeof(Variant) is 24. On most platforms, int has a maximum value of 2147483647 which is smaller than 100000000 * 24 = 2400000000. This means, the multiplication does an overflow.

How to solve this bug? Well, first step would be to use the more proper type size_t. But even size_t allows for overflow. Best would be to check the multiplications and additions. I'm preparing a patch right now that does precisely this.

[sheepandshepherd]

Still, it's not sane to allocate 2.4GB of memory just for a loop.
If we want to keep range creating an array to iterate over, it should probably not be allowed to go as high as 100mil at all. A better solution than arbitrary limits would be to implement range as a real iterator object, which Godot already supports (see explanation on issue #3765). I can make a PR with a "RangeIterator", but we should discuss if that's the right way of dealing with it first. It could have a function to create an array (what it does now), but I don't think that should be the default behavior of range.

[est31]

Yes, having range as iterator (at least for usage in for loops) would be a great addition too, even though it doesnt fix the same bugs as 3771 (which will still happen if you try to construct an array from range). Probably there should be some care taken to avoid breakage when people want to use its return value as normal value, dont know how godot handles breaking api changes.

[sheepandshepherd]

Yeah, that'd be a breaking change for sure. There's no easy way to make range act differently in a for loop than in a variable assignment. Could just add the iterator as a new class, but leave range as it is.