What is the difference between user stack and embedded stack when using memory?

Question

I want to use a user-defined stack for my program that has a large number of recursive calls? Would it be useful to define a user-defined stack?

Answer 1

There are several ways to do this.

First of all, two:

(1) Use the processor / processor stack. There are several options, each with its own limitations.

(2) Or, recode your functions to use a stack structure that mimics a "stack." The actual function ceases to be recursive. It can be almost limitless until the heap allows

---

For (1) ...

(A) If your system allows, you can issue syscall to expand the process stack size. There may be restrictions on how much you can do this, and collisions with shared library addresses.

(B) You can malloc large area. With some [somewhat] complex intrigues of asm trickery, you can exchange this area for the stack [and vice versa] and call your function with this area malloc as a stack. Reason, but not for the faint of heart ...

(C) An easier way is to malloc large area. Go through this area to pthread_attr_setstack . Then run your recursive function as a thread using pthread_create . Please note that you do not really care about multiple threads, this is just an easy way to avoid the "messy" azma. Asm trickery.

C (A), assuming that the permission for stop expansion can be increased, the limit can be all available memory allowed for the stack [up to some system-wide or RLIMIT_ * parameter].

With (B) and (C) you need to “guess” and make malloc big enough before you start. After this is done, the size will be fixed and cannot be expanded further.

Actually, this is not entirely true. Reusing asm tricks [if necessary], you can simulate an almost endless stack. But, IMO, the overhead of tracking these large malloc areas is high enough for me to prefer (2) below.

---

For (2) ...

It can literally expand / contract as needed. One of the advantages is that you do not need to guess in advance how much memory you will need. [Pseudo] stack can just keep growing as needed [until malloc returns NULL ].

Here is an example of a recursive function [treat free as pseudocode]:

 int myfunc(int a,int b,int c,int d) { int ret; // do some stuff ... if (must_recurse) ret = myfunc(a + 5,b + 7,c - 6,d + 8); else ret = 0; return ret; } 

This function has changed to use struct as a stack frame [again, free pseudo-code]:

 typedef struct stack_frame frame_t; struct stack_frame { frame_t *prev; int a; int b; int c; int d; }; stack_t *free_pool; #define GROWCOUNT 1000 frame_t * frame_push(frame_t *prev) { frame_t *cur; // NOTE: we can maintain a free pool ... while (1) { cur = free_pool; if (cur != NULL) { free_pool = cur->prev; break; } // refill free pool from heap ... free_pool = calloc(GROWCOUNT,sizeof(stack_t)); if (free_pool == NULL) { printf("frame_push: no memory\n"); exit(1); } cur = free_pool; for (int count = GROWCOUNT; count > 0; --count, ++cur) cur->prev = cur + 1; cur->prev = NULL; } if (prev != NULL) { *cur = *prev; cur->prev = prev; cur->a += 5; cur->b += 7; cur->c += 6; cur->d += 8; } else memset(cur,0,sizeof(frame_t)); return cur; } frame_t * frame_pop(frame_t *cur) { frame_t *prev; prev = cur->prev; cur->prev = free_pool; free_pool = cur; return prev; } int myfunc(void) { int ret; stack_t *cur; cur = frame_push(NULL); // set initial conditions in cur... while (1) { // do stuff ... if (must_recurse) { cur = frame_push(cur); must_recurse = 0; continue; } // pop stack cur = frame_pop(cur); if (cur == NULL) break; } return ret; } 

Answer 2

All functions, objects, variables, and user-defined structures use memory space, which is the OS control and compiler. Thus, your specific stack runs under the shared memory space that is specified for the stack of your process in the OS. As a result, this does not really matter, but you can define an optimized structure with high efficiency to use this common stack much better.