Minimal implementation of a call stack on the heap in C-CodePudding

This is a pretty vague question and I apologise in advance but I want to know if I were to implement the stack of activation frames, on the heap, where do I begin?

For example:

int factorial(int n)
{
    if(n == 0) return 1;
    return n * factorial(n - 1); 
}
// say n = 5

The above code would result in 5 activation frames being pushed onto the program stack, each having the appropriate local parameters, return addresses etc.

If I were to know 'n' in prior, and I'm able to allocate an array of 'n' contiguous blocks on the heap (using malloc), how can I store and execute the subroutines in each such block?

The main goal is to curb the number of activation frames. For ex if 'n' here is huge enough to cause stack overflow, the program crashes. But if I somehow store the snapshot of an activation frame at runtime, into my Data structure on the heap, and compute the end value, there's a good possibility of the program not crashing. And it's not like I want to dive deep into assembly level code when I mention the snapshot.

You might be wondering how the stack overflow is eliminated after doing this, that's to be done by using setjmp and longjmp, using the activation frames for LIMIT number of times, in the manner of a trampoline. Going up : use the stack frames until LIMIT reached; once reached going down using longjmp.

CodePudding user response：

You can replace recursions with loops and arrays. Arrays that store that values which would otherwise be stored on the stack. This can get difficult for some functions. Here is an example with a code that does the same as your code but on loops and a array, i tried to be as close to the original code as possible, it can be simplified a lot and the array is not really needed. But your code compiled with a naive compiler would also store the values in a array like object, an array of stack frames, so i use an array.

int factorial(int n)
{
    int storageArray[5]; //This values are stored on the stack frames in the orginal, one value per stack frame
    size_t index=0; //This is comparable with the call depth
    while(1) //loop that simulates the calls to function
    {  
        if(n == 0) break; //We are at the deepest call that returns
        storageArray[index]=n;
        n=n-1;
        index  ;
    }
    int returnValue=1; //the deepest function returns 1.
    while(index--) //loop that simulates the returnings from the function
    {   //storageArray[index] is named n in your function.
        returnValue=returnValue*storageArray[index];
    }
    return n; 
}

If that gets too hard, you could try to get a bigger stack, for Linux: Change stack size for a C application in Linux during compilation with GNU compiler or you could use a interpreted language where the stack is stored in a array and the maximum depth can be controlled, for example python.

CodePudding user response：

if I were to implement the stack of activation frames, on the heap, where do I begin?

You would begin by writing your code in assembly rather than in C. The C language does not provide any mechanism for program control over where the stack is for a given function call. In fact, it does not even assume the existence of a stack in the first place.