Manage heap's stack for recursive functions at run time

[cristian-ilies-vasile]

A small proof of concept code written in C and Assembly in order to manage heap allocated stack for recursive functions.

/* 
 * swap_stacks_poc.c
 * 
 * Manage huge stack at run time for recursive functions calls
 * A ->B ->C ->D ->B ->C ->D ->B ...
 *
 * Proof of Concept / 29.08.2020 
 * 
 * nice to have: code to check the heap stack increase and re-allocate memory at run time
 * 
 */

#include <stdlib.h>   
#include <stdio.h>   

int fn_a(int a, int b);
int fn_b(int a, int b, int c);
int fn_c(int a, int b);
int fn_d(int a, int b);

int fn_d(int a, int b)           
{
    int result;
	int first_call = 1;                    // 1 = fn_b is called n times, in a recursive way 
    printf("fn_d\n");
	result = 4*(a+b);
    if (result < 1000000) {
        fn_b(result,2,first_call);         // recursive call of fn_b		
    } 	
	return result;                         
} 

int fn_c(int a, int b)                       
{
    int result, from_d;
    printf("fn_c\n");
	result = 3*(a+b);
	from_d = fn_d(result, 2);
    return result;                             
} 
 
int fn_b(int a, int b, int first_call)            
{
    int result, from_c, k;
	char *ptr_new_stack_end    = (char *) 0;                      // save here for free()
    char *ptr_new_top_of_stack = (char *) 0;
	long long int new_stack_end = 0;                                          
	long long int x_bp = 0, x_sp = 0;
	long long int           y_sp = 0;
	long long int marker =0;
	
	printf("fn_b\n");printf("fn_b a=%d\n", a);	printf("fn_b b=%d\n", b); 

	if (first_call == 0) {
		printf("fn_b first call\n");
		k = (8*1024*1024);                                                         // 8M of chars/bytes 
		ptr_new_stack_end = (char *) malloc(k * sizeof(char));                     // get memory  
	    printf("k= %d\n",k); printf("k*1= %d\n",k*1);
		new_stack_end = (long long int) ptr_new_stack_end;
		
		printf("ptr_new_stack_end = %d\n", ptr_new_stack_end);
	    printf("new_stack_end = %d\n", new_stack_end);
		
		/*
		 * Stack Pointer goes from High to Low
		 * 4    chars room for space
		 * 1024 chars room to copy a piece of fn_a's stack on fn_b's stack
		 */ 
	
		// ptr_new_top_of_stack = (char *) (((int) ptr_new_stack_end + (k-4-1024) * sizeof(char)) ); 
		ptr_new_top_of_stack = (char *) ((new_stack_end + (k-4-1024) * sizeof(char)));
		ptr_new_top_of_stack = (char *) (((((int)ptr_new_top_of_stack ) >> 7) -1 ) << 7);            // align at 128 bits for CPU cache lines
		printf("ptr_new_top_of_stack = %d\n", ptr_new_top_of_stack);
		
		printf("&ptr_new_stack_end[0] = %p\n", &ptr_new_stack_end[0]);
		printf("&ptr_new_stack_end[1] = %p\n", &ptr_new_stack_end[1]);
		printf("&ptr_new_stack_end[2] = %p\n", &ptr_new_stack_end[2]);
		
		printf("start stack \n");
		// we shall replace stack here 
		// 64 bit for testing
		__asm__ __volatile__ (
			// "pushq %%rax               \n\t"
			// "pushq %%rbx               \n\t"
			// "pushq %%rbp               \n\t"
			//"movq  %%rsp, %%rbp        \n\t"                           // move stack pointer in base pointer
		    
			"movq  $0x20, %%rdi          \n\t"                             // testing asm
			"movq  $0x40, %%rsi          \n\t"                             // testing asm
			
			"movq  %%rbp, %%rdi        \n\t"                           // rbp -> rax
			"movq  %%rsp, %%rsi        \n\t"                           // rsp -> rbx
			
			// "movq  %%rax, %0           \n\t"
			// "movq  %%rbx, %1           \n\t"
			"movq  %%rdi, %[cpu_rbp]           \n\t"
			"movq  %%rsi, %[cpu_rsp]           \n\t"
			
			// "movq 8(%%rsp), %%rcx              \n\t"
			// "movq %%rcx, %[cpu_marker]           \n\t"
			
			//"movq  %%rbp, %%rsp        \n\t"                           // restore stack pointer
			// "popq  %%rbp               \n\t"
			// "popq  %%rbx               \n\t"
			// "popq  %%rax"
			
			 : [cpu_rbp] "=r" ( x_bp ), [cpu_rsp]"=r" ( x_sp )             // , [cpu_marker] "=r" (marker)                                           	/* output */
			 : 
			 : "rdi", "rsi"                                                             
		);
		printf("ptr_new_stack_end x_bp after movq  rcx = %d\n", x_bp);
		printf("ptr_new_stack_end x_sp after movq  rdx = %d\n", x_sp);
		
		/*
		 * mirror last 1000 bytes from current stack on new stack
		 * void *memcpy(void *dest, const void * src, size_t n)
		 */   		 
		memcpy(ptr_new_top_of_stack, x_sp, 1000);
		printf("ptr_new_top_of_stack after memcopy = %d\n", ptr_new_top_of_stack);
		
		// change stack pointer here		     
		__asm__ __volatile__ (
			"movq %[cpu_rsp], %%rsi                               \n\t"
			"movq %%rsi, %%rsp                                    \n\t"
		:
		: [cpu_rsp] "r" ( ptr_new_top_of_stack )                      // input
		);
		
		printf("SP contains new top of stack \n");
	}
	result = 2*(a+b); printf("fn_b result line 118 =%d\n", result);        // should be 12 on last return 
	from_c = fn_c(result, 2);
	printf("from_c = %d\n", from_c);
    
	// check for stack signature
	__asm__ __volatile__ (
		"movq  %%rsp, %[cpu_rsp]        \n\t"
		: [cpu_rsp] "=r" ( y_sp )
	);
	
    printf("y_sp =%d\n", y_sp); 

    if ((long long int) ptr_new_top_of_stack == y_sp ) {
	printf("try to restore SP here\n");	
	// OK, switch on the real stack
	__asm__ __volatile__ (
		
		//"movq 8(%%rsp), %%rdi                                 \n\t"
	    //"movq %[cpu_marker], %%rsi                            \n\t"
		
		//"cmpq %%rdi, %%rsi                                    \n\t"
		//"jne DONE                                             \n\t"
		"movq %[cpu_rbp], %%rdi                               \n\t"
		"movq %[cpu_rsp], %%rsi                               \n\t"
		
		"movq %%rdi, %%rbp                                    \n\t"
		"movq %%rsi, %%rsp                                    \n\t"
		//"DONE: nop                                            \n\t"	
		:
		: [cpu_rbp] "r" ( x_bp ), [cpu_rsp] "r" ( x_sp )               // , [cpu_marker] "r" (marker)		// input
		: "rdi", "rsi"
		);
	free(ptr_new_stack_end);
	}		
	
	printf("fn_b a=%d\n", a);	printf("fn_b b=%d\n", b); 
	return 2*(a+b);                           // recompute return value based on vars stored on initial stack, the ones placed by fn_a
	
} 

int fn_a(int a, int b)                            
{
    int result, from_b;
	int first_call = 0;                        // call fn_b first time from fn_a
    printf("fn_a\n");
	result = 1*(a+b);
	from_b = fn_b(a,b, first_call);
	printf("from_b = %d\n", from_b);
    return result;                             
}
int main()
{ 
    int a, from_a;
	printf("start main()\n");
	from_a = fn_a(2,4);
	printf("from_a = %d\n", from_a);
	printf("end main()\n");
    return 0;
}

[UweKrueger]

I'm not quite sure what the intention of this issue is. Providing a more specific description what problem you want to solve and putting your code into a ```C ... ``` block (so it is formatted) would have been helpful...
I presume that you want a stack that can dynamically grow using heap memory to allow allow large stack allocations and almost infinite recursions. Well, there are 2 things to consider:

• You are not the first one having this idea. Actually there has been the gcc command line option -fsplit-stack for years that does exactly this automatically - so there is no need to write extra code for that.
• This command line option is not used by default (and not for glibc) since both allocating large memory blocks on the stack and doing unlimited recursions are considered a bad programming style and usually people want their program to crash in the development phase if such a condition occurs.

That said gccgo does use this flag by default AFIAK, since having no stack overflows is a defined Go feature.

However, when people talk about memory management they usually refer to heap memory - in a multi threaded environment.

[cristian-ilies-vasile]

I did reformat the layout. with three backticks.

The idea is to use a heap allocated stack only for recursive function calls, and then revert back on original stack after the recursive chain of calls is completed.

I know that calling functions in recursive loop is not a good programming practice , but this task & PoC were created based on this Discord's request/proposal https://discord.com/channels/592103645835821068/713909145899630632/748578143413207172 because other language is able to perform such trick.

-fsplit-stack
Generate code to automatically split the stack before it overflows. The resulting program has a discontiguous stack which can only overflow if the program is unable to allocate any more memory. This is most useful when running threaded programs, as it is no longer necessary to calculate a good stack size to use for each thread. This is currently only implemented for the x86 targets running GNU/Linux.

When code compiled with -fsplit-stack calls code compiled without -fsplit-stack, there may not be much stack space available for the latter code to run. If compiling all code, including library code, with -fsplit-stack is not an option, then the linker can fix up these calls so that the code compiled without -fsplit-stack always has a large stack. Support for this is implemented in the gold linker in GNU binutils release 2.21 and later.

[cristian-ilies-vasile]

-fsplit-stack
This option seems to be useful for multi threaded code, not for the matter described on Discord.

Also this trick with 2 stacks could be useful for future "-autofree" V's compiler flag aka automatic memory management.
Is hard to compute lifetimes for objects allocated on heap, which in turn are used in recursive loops. Might the trick with 2 stacks can help on triggering free() for each such object.