Call Stack Memory Management

pseudosig · 07-23-2008, 01:35 PM

Not being versed in the linux kernel, I apologize ahead of time if this isn't a proper question in the kernel section.

Here's my problem:

I have algorithms coded in c++ that are very recursive in nature. This is something I'll probably not be able to change. So given this, I noticed something peculiar when I execute my code. Here's a sample program and analysis of what I'm experiencing...

Code:

#include <iostream>
#include <QApplication>
using namespace std;

int c = 0;
void RecursiveFunction(int n);

/*--------------------------------------------------------------------------*/
int main(int argc, char** argv)
{      
      qDebug("::1");
      RecursiveFunction(1);
      qDebug("::2");
      sleep(5);


      c = 0;
      qDebug("::3");
      RecursiveFunction(2);
      qDebug("::4");
      sleep(300);
      
      return 0;
}
/*--------------------------------------------------------------------------*/

void RecursiveFunction(int n)
{
      c++;
      if(c > 1000000*n)
      {
         return;
      }
      else
      {
         void (*fPtr)(int) = RecursiveFunction;
         fPtr(n);
      }
}

Here's the standard error and top output...

Code:

./mem_test 
::1
::2

... after the "::2", here's what top outputs...
  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND            
11680 pseudosig 20   0 48200  33m 2432 S    0  1.2   0:00.04 mem_test



./mem_test 
::1
::2
::3
::4

... after the "::4", here's what top outputs...
  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
11680 pseudosig 20   0 79452  63m 2432 S    0  2.3   0:00.10 mem_test

Okay, so after the recursive function gets called the first time in main, it grows the stack (I'm assuming call stack) by 33m, and then after it fully returns and is sleeping after "::2", the stack doesn't resize back down. Then the same happens after the "::4" line, but by 2 fold.

My problem is that my recursive functions are consuming memory (from the call stack?) and after the recursion fully returns, the size of the call stack seems to stay the same, even though I'm sure the function has been popped off the call stack. How can I dynamically trim the stack after the recursive function calls have happened... or can I?

Thanks....

kundor · 07-23-2008, 01:54 PM

The stack isn't returned to the OS. But it will be reused by your program.

That is, the C++ runtime will allocate memory as necessary to grow the stack. When a function returns, it moves the stack pointer back down, but it doesn't return the frame to the OS. (If it did, functions calls would be unbearably slow. Besides, what's the kernel going to do with it? Give it to some other program, when it's almost certain you're going to grow into that space again?) When you put more stuff on the stack, it grows through the area that's already been allocated. When it hits the ceiling again, it will allocate more from the OS.

So this is what you'd expect to see. It's fine, unless you grew a ton of stack, then returned, and you know you won't be using it again, and you have a burning concern for the memory needs of other programs on the system.

(Caveat: This is my understanding, but I don't really know what I'm talking about.)

pseudosig · 07-23-2008, 01:59 PM

Quote:

Originally Posted by kundor

The stack isn't returned to the OS. But it will be reused by your program.

That is, the C++ runtime will allocate memory as necessary to grow the stack. When the function returns, it moves the stack pointer back down, but it doesn't return the frame to the OS. (If it did, functions calls would be unbearably slow.) When you put more stuff on the stack, it grows through the area that's already been allocated. When it hits the ceiling again, it will allocate more from the OS.

So this is what you'd expect to see. It's fine, unless you grew a ton of stack, then returned, and you know you won't be using it again, and you have a burning concern for the memory needs of other programs on the system.

(Caveat: This is my understanding, but I don't really know what I'm talking about.)

That makes sense. But is there a way to return frames that aren't in the scope of the current stack pointer in linux?

sundialsvcs · 07-24-2008, 09:04 AM

The stack grows. In a user-land program, operating in virtual memory, unused stack-space simply gets paged-out and forgotten.

Kernel-mode programs do not have liberal amounts of stack space at their disposal.

kundor · 07-26-2008, 12:34 PM

Well, you can do this by playing with pthreads.

Code:

#include <stdio.h>
#include <pthread.h>
#include <errno.h>
#include <unistd.h>

static int c = 0;
static const size_t stacksize = 128 * 1024 * 1024;
static const int depth = 1000000;

void recurse(int n) {
      if (++c > depth*n) {
         return;
      } else {
         void (*fPtr)(int) = recurse;
         fPtr(n);
      }
}

void* recurseParent(void* n) {
    recurse((int) n);
    fprintf(stderr, "--All done (%d)\n", (int)n);
    sleep(4);
    return (void*) 0;
}

void err(int result) {
    static int count = 0;
    ++count;
    if (result) {
        fprintf(stderr, "\n%d : %d\n", count, result);
    }
}

int main() {
    pthread_attr_t attr;
    pthread_t recursethread;
    void *retval;

    err( pthread_attr_init(&attr) );
    err( pthread_attr_setstacksize(&attr, stacksize) );
    err( pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE) );

    sleep(4);

    fprintf(stderr, ":1\n");
    err( pthread_create(&recursethread, &attr, recurseParent, (void*) 1) );
    err( pthread_join(recursethread, &retval) ); //wait for completion
    fprintf(stderr, ":2\n");

    sleep(4);

    fprintf(stderr, ":3\n");
    c = 0;
    err( pthread_create(&recursethread, &attr, recurseParent, (void*) 2) );
    err( pthread_join(recursethread, &retval) ); //wait for completion
    fprintf(stderr, ":4\n");

    sleep(4);

    err( pthread_attr_destroy(&attr) );

    return 0;
}

This is the output:
:1
--All done (1)
:2
:3
--All done (2)
:4

And with output from top interspersed at the appropriate times:

Code:

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
 1908 kundor    20   0  1492  352  288 S  0.0  0.0   0:00.00 threader
:1
--All done (1)
 1908 kundor    20   0  129m  30m  392 S  0.0  3.5   0:00.10 threader
:2
 1908 kundor    20   0  1624  464  396 S  0.0  0.1   0:00.11 threader
:3
--All done (2)
 1908 kundor    20   0  129m  61m  396 S  0.0  7.0   0:00.36 threader
:4
 1908 kundor    20   0  1624  464  396 S  0.0  0.1   0:00.37 threader

As sundialsvcs mentioned, this is unlikely to provide much benefit.

P.S. compiled with "gcc -pthread -o threader threader.c"

pseudosig · 07-31-2008, 08:20 AM

Okay... so I've spent a little more time with this problem. It turns out that my memory consumption problem has more than just recursive function calls as root of the problem. If you allocate a huge chunk of memory and delete/free it... then some of the memory space handed to the application from the kernel is given back to the kernel, but in general most of it is retained still by the application. This seems to be true for both the call stack and "heaped" memory.

I did seem to find a partial (if not total) solution. I've been digging around in <sys/mman.h>, which encompasses memory management declarations. There's a function madvise (int madvise(void *start, size_t length, int advice) ) that has a parameter option MADV_DONTNEED that "advises" the kernel that you probably won't need a certain memory block/range... so take it back. In the case of linux, the function call is less than a suggestion and more like a command. My problem now is how does one track their memory allocation so one could hand memory chunks back to the kernel? More specifically, how does one know what memory chunks for void *start and size_t length map to a recently allocated object?

Anyone had experience with this? Any suggestions are appreciated...

pseudosig · 10-03-2008, 12:03 PM

A solution to this already exists. There's a library called jemalloc that has a different memory allocator than just the standard C mallocl/etc (it's now in firefox 3.0) and it dynamically hands memory back and forth to the kernal, instead of just growing.

All you have to do is link against the library at compile time or runtime, and all is good. I've been using it for a while now... and it rocks.