baffling crash

Posted By: txesmi

baffling crash - 10/03/13 21:01

How can this crash in main?

Code:

#include <acknex.h>

#define INTARRAY    128

void main ()
{
	var array[INTARRAY][INTARRAY];
	var i, ii;
	
	for ( i=0; i<INTARRAY; i+=1 )
	{
		for ( ii=0; ii<INTARRAY; ii+=1 )
		{
			array[i][ii] = maxv ( i/INTARRAY, ii/INTARRAY );
		}
	}
	
	while ( !key_esc )
	{
		wait(1);
	}
	
	sys_exit ( NULL );
}

Could someone test it in order to know if it is my pc problem? I can't increase the array size without a crash... I can't believe it

Posted By: xbox

Re: baffling crash - 10/03/13 22:11

I just tried it on my pc, and through placing beeps after every line, it is crashing at the very beginning of the first for loop, more precisely on this line.

Code:

for ( i=0; i<INTARRAY; i+=1 )

Posted By: Uhrwerk

Re: baffling crash - 10/04/13 00:35

It works with 127, but crashes with 128. If you sum up the required memory it is 128 * 128 * 4 bytes = 65536 bytes = 64 kbytes. I guess that's the maximum stack size. You shouldn't allocate such arrays on the stack anyways.

Just make array a global variable or allocate it with sys_malloc and release it with sys_free.

Posted By: Superku

Re: baffling crash - 10/04/13 06:49

Exactly, the manual says the same as Uhrwerk:

Originally Posted By: Variables

Be careful when defining huge local arrays. All local variables are stored on a special memory area called the stack. This area has a limited size that depends on where your function is running and whether it's called by other functions. Exceeding the stack size causes any program to crash . Thus, when you need huge local arrays of ten thousands of variables, or when you want to determine the array size dynamically, use the sys_malloc / sys_free method.

I had to learn this limitation myself the hard way: Many years ago I worked on a puzzle solving algorithm with lite-C and I could not understand why it crashed or even "went the wrong way" on the puzzle board after some 100 iterations. It took me quite literally multiple days to find out that the local array declaration of a function in my recursive program would fail without notice after a certain recursive depth.

Posted By: txesmi

Re: baffling crash - 10/04/13 07:41

fvk, man, what a rookie failure. I should think about the limit of the stack. I feel like a absolute noob right now. Earth, swallow me!

Lots of thanks for your answers.

Posted By: Uhrwerk

Re: baffling crash - 10/04/13 11:59

Originally Posted By: txesmi

I feel like a absolute noob right now. Earth, swallow me!

Don't feel bad. This can happen to anybody. Especially if you're used to a managed programming language where none of this stuff gets placed on the stack with the exception of the corresponding reference.

Posted By: oliver2s

Re: baffling crash - 10/04/13 12:27

Does it always crash immediatly if I exceed the stack or can I also get a crash somewhere later in the script?

Posted By: Uhrwerk

Re: baffling crash - 10/04/13 13:15

I guess(!) exceeding the stack's size always crashes immediately. (Overwriting random memory could also be an option according to my lite-c experiences. ^^) But to be sure I'd suggest asking jcl.

Posted By: WretchedSid

Re: baffling crash - 10/04/13 14:06

I tried to get anything meaningful out of the MSDN, but it doesn't appear like the last map of the stack is unmapped intentionally. So you might very well end up with memory corruption upon a stack overflow instead of a segfault.

Edit: Write your own test case: Create a recursive function and call it repeatedly. Each recursion will add 8 bytes on the stack, simply look how far down the rabbit hole you get before it crashes. I don't think that Lite-C supports tail-call optimization, but if it does, simply thwart it by making another call into anything that the compiler only has the declaration of.

Posted By: irchel2

Re: baffling crash - 10/04/13 17:51

I'd give malloc() a shot. It allocates memory on the heap instead of the stack. Look up a C language documentation how to use it.

You would have to use int instead of var then, I presume. Leave a note if you want me to figure out an exact implementation for it.

Posted By: Rackscha

Re: baffling crash - 10/04/13 18:45

Please keep in mind that the 64kb limitation is a limitation of Lite-C. Other Compilers set the limit to 1MB.(i.e. Delphi, and i am sure other C and C++ compilers do the same)

Posted By: Uhrwerk

Re: baffling crash - 10/04/13 19:19

Originally Posted By: irchel2

I'd give malloc() a shot. It allocates memory on the heap instead of the stack. Look up a C language documentation how to use it.

Don't use malloc. Use sys_malloc in lite-c as I suggested above.

Originally Posted By: irchel2

You would have to use int instead of var then, I presume.

The type of the variable is totally irrelevant for sys_malloc / malloc.

Posted By: Superku

Re: baffling crash - 10/05/13 08:00

As I've written in my post above it does not crash immediately, at least it did not in my case. Over a couple of years every now and then I tried a different puzzle solving algorithm (for the puzzle "Eternity II"), for instance one that would trace the board in a spiral:

The recursive structure of my first algorithm used a function as follows:

void solve_step(...)
{
var tile_array[1024];
var used[256];
...
}

It seemed to worked flawlessly until a good number of pieces had been placed but then it would just go into a wrong direction for a couple of pieces (for no apparent reason) before crashing.

Posted By: WretchedSid

Re: baffling crash - 10/05/13 08:54

I know it's not on topic in the purest form of on-topicness, but the way this is usually solved, is by changing your algorithm so that it uses a loop instead of recursion. Granted, that isn't always possible, in which case you have to fallback to recursion and allocation on the heap.

The first solution works great when you have only values that are further used when you go down the rabbit hole, like in this classic example for recursion:

Code:

int factorial(int n)
{
    if(!n)
        return 1;
    
    return n * factorial(n - 1);
}

Using a sophisticated compiler, you will end up with no recursion at all since your function would become victim of tail-call optimization. However, it's trivial to rewrite this using a loop:

Code:

int factorial(int n)
{
    int fact = 1;
    
    for(; n >= 1; n --)
        fact *= n;
        
    return fact;
}

Granted, for the sake of it I chose a really trivial example. But you should get the gist of it. Also take the following away: The stack isn't meant to hold huge allocations. Don't use it for that. Everything bigger than a hundred bytes probably belong better on the heap (there are exceptions, but yeah, rule of thumbs).