What is a call stack?

I am not clear what all data gets stored in a stack when one function calls the other in C++ during a single-thread and a multi-threaded environment.
sukhoi35Asked:
Who is Participating?
 
eagerConnect With a Mentor Commented:
The call stack is an area of memory used by your program.  The stack starts out empty and new chunks are allocated when you enter each function. These chunks are called "frames".  A frame contains the following:  return address for the function, link to the previous frame, and local variables.  (Smart compilers have ways to optimize this so that some or all of these may be omitted or saved in registers.)

When one function calls another, the arguments are added to the stack before calling the second function. This second function will create a new frame on the call stack, immediately after the arguments.  When a function returns, it's frame is removed from the stack.

It's called a stack because it figuratively looks like a stack of plates.  Each frame is a new plate added on the top of the stack while a return removes one.  The call stack contains the history of the program, showing exactly how it got to the current function.

In a multi-thread environment, each thread has it's own independent stack, created when the thread is created.  Otherwise, the call stack looks the same.  
0
 
phoffricCommented:
int foobar(int x, int y) {
    x = x+2;
    return x+y;
}

This function takes two variables that, in this case, are passed by value onto the foobar's stack. The stack will contain two int values corresponding to x and y. foobar will treat these two variables on the stack as local variables, so even though x was incremented by 2, the caller will not see that change. The change in x is only known within the foobar routine.

When the function returns, the stack is gone and no values on the stack memory should be considered valid.
0
 
phoffricCommented:
http://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html

In this tutorial on POSIX threads, you see that the  pthread_create() creates a new thread. It's last arg is void *arg, where:
  "*arg - pointer to argument of function. To pass multiple arguments, send a pointer to a structure"

Example:
iret1 = pthread_create( &thread1, NULL, print_message_function, (void*) message1);
void *print_message_function( void *ptr )
{
     char *message;
     message = (char *) ptr;
     printf("%s \n", message);
}
pthread_create has message1 as the argument to be passed to the thread,  print_message_function; and this argument is passed on the stack as you can see in the print_message_function function thread.
0
Cloud Class® Course: CompTIA Healthcare IT Tech

This course will help prep you to earn the CompTIA Healthcare IT Technician certification showing that you have the knowledge and skills needed to succeed in installing, managing, and troubleshooting IT systems in medical and clinical settings.

 
Infinity08Connect With a Mentor Commented:
The important things to know about a call stack, is that :

(a) it's handled by the compiler for you, so you usually don't need to worry yourself with it (except to know that it's there, and how it works in big lines).

(b) there usually is one call stack for each thread in a process (so threads don't step on each other's toes).

The purpose of a call stack is to keep track of all nested function calls by adding a stack frame for each function call onto the stack, and removing it again when the function ends. Each stack frame contains whatever information is needed to describe the function call. This usually includes function arguments, function local variables and the function return address.

All this however varies from platform to platform (and also depends on the specific calling convention used for making the function call). So if you need to know how it's handled specifically in your case, check your platform/compiler documentation.
0
 
sukhoi35Author Commented:


Infinity08 >> "This usually includes function arguments, function local variables and the function return address."

But according to the Phoffric's example above, only the arguments of the caller are stored in the stack. Can you  please clarify which is the right method?
0
 
Infinity08Commented:
The right method is whatever the calling convention / platform / compiler require.

As far as I can tell, phoffric interpreted your question in a different way. It seems he just talked about function arguments, while I was talking about the call stack.
0
 
Infinity08Commented:
@eager : I think you'll find that your post doesn't add much to what I already posted ;)
0
 
phoffricConnect With a Mentor Commented:
Since you mentioned multi-threading in your OP, I may have inferred incorrectly that you already knew about stacks, and was just concerned about how arguments are passed onto a thread's stack.

The common issue is that a program may have been initially built for a single thread. But when multi-core processors came around, it became desirable to try to reuse as much as possible the same functions running in multiple threads. (There are usually synchronization issues in doing this, but one item to tackle in porting from single to multiple threads is getting the arguments onto the thread's call stack.)

As mentioned earlier, only one void * arg is permitted to be placed on the thread's call stack for the starting routine when using the pthread_create function. One formula way to handle this is to wrap the desired function with a start routine that effectively takes a pointer to a stack that has the arguments, and then passes these args to the function.

If you are interested in exploring the stack layouts of the passed arguments in the main thread as well as spawned threads, here is an example where two functionally identical functions, foobar and fooTHR, are used. The output on Cygwin is:
$ g++ argPassing.c ; ./a
main:  &ret1  = 0022cd38  &ret2  = 0022cd34  &res1 = 0022cd30  &res2 = 0022cd2c
main:  &args1 = 0022cd24  &args2 = 0022cd1c  &th1  = 0022cd18  &th2  = 0022cd14

foobar: &tmp  = 0022cce4      &x = 0022ccd4    &y = 0022ccd0    &z = 0022ccf8
foobar: &tmp  = 0022cce4      &x = 0022ccd4    &y = 0022ccd0    &z = 0022ccf8
fooTHR: &farg = 1885cd80    &ptr = 1885cd74  &tmp = 1885cd70
fooTHR: &farg = 18a5cd80    &ptr = 18a5cd74  &tmp = 18a5cd70
 sum1 = 45  sum2 = 450   res1 = 45   res2 = 450

Open in new window

The above debug shows the address of the main's stack (local variables), foobar's stack (on the main thread) showing passed args and local auto variables; and the start routine's stacks on two separate threads.

The method of returning a value using the 2nd status argument of pthread_join isn't 100% portable; so use under advisement.
#include <pthread.h> 
#include <stdio.h> 
#include <unistd.h>

long foobar(unsigned char x, unsigned short y, unsigned long z) {
    unsigned long tmp = x+y+z;
    printf("foobar: &tmp  = %08x      &x = %08x    &y = %08x    &z = %08x\n", &tmp, &x, &y, &z);
    return tmp;
}

struct foobarArgs {
    unsigned char  x;
    unsigned short y;
    unsigned long  z;
};

void * fooTHR( void *farg ) {
    foobarArgs * ptr = (foobarArgs *) farg;
    long tmp = ptr->x + ptr->y + ptr->z;
    sleep(1);
    printf("fooTHR: &farg = %08x    &ptr = %08x  &tmp = %08x\n", &farg, &ptr, &tmp);
    return (void*)tmp;
}

int main () 
{
  int ret1;
  int ret2;
  unsigned long res1;
  unsigned long res2;

  foobarArgs args1 = {20,15,10}; 
  foobarArgs args2 = {200,150,100};
  pthread_t th1; 
  pthread_t th2;

  unsigned long sum1;
  unsigned long sum2;

  printf("main:  &ret1  = %08x  &ret2  = %08x  &res1 = %08x  &res2 = %08x\n"
         "main:  &args1 = %08x  &args2 = %08x  &th1  = %08x  &th2  = %08x "
               "\n\n",
               &ret1,   &ret2, &res1, &res2,
               &args1,  &args2, &th1, &th2 );
  
  sum1 = foobar(20,15,10);

  ret1 = pthread_create  (&th1,  NULL,  fooTHR,  &args1);
  if( 0 != ret1 ) {
      perror("thread 1");
  }
  ret2 = pthread_create  (&th2,  NULL,  fooTHR,  &args2);
  if( 0 != ret2 ) {
      perror("thread 2");
  }

  sum2 = foobar(200,150,100);
  
  pthread_join(th1,  (void**)&res1);
  pthread_join(th2,  (void**)&res2);

  printf(" sum1 = %ld  sum2 = %ld   res1 = %ld   res2 = %ld\n", sum1, sum2, res1, res2);
 
  return  0; 
}

Open in new window

0
 
Infinity08Commented:
>> the main's stack (local variables), foobar's stack (on the main thread)

I have to ask now : what do you mean by this ? On most (if not all) platforms, both stack frames for the main and foobar function calls will be on the SAME stack. It wouldn't make sense to put every function call on a separate stack.

I'm starting to understand that there's a confusion/misunderstanding somewhere. Either :

(a) the asker used the term "call stack" incorrectly to refer to the arguments that need to be passed to a thread. And you (phoffric) correctly inferred that misunderstanding, and gave the answer accordingly (albeit not correcting the incorrect usage of the term "call stack")

(b) or the asker was actually asking about the call stack, and then the confusion seems to be on your (phoffric's) end, in which case your responses are possibly causing some confusion for the asker ;)


@sukhoi35 : could you clarify the question, please ? Were you actually talking about the call stack (http://en.wikipedia.org/wiki/Call_stack), or about something else ?
0
 
phoffricCommented:
Just to clarify my too loose terminology. In the code example, there are 3 stacks, one for the main thread and one for each of the two spawned threads.

The main thread's stack has three call frames created, one for the main function, and one for each of the two invocations of foobar. (In both of these foobar call frames, the call frame is the same with same addresses, since that frame was released after the first foobar returned.)

The two spawned thread's stacks are 2MB apart (in virtual address space, not in physical memory distance).
0
 
eagerConnect With a Mentor Commented:
Phoffric -- I think the exercise in pthreads is a bit different from the question the OP asked.  But as long as you are running down this rathole, please note the following:  

Main calls foobar at two different times, each of which creates a frame.  The frames created for the calls to foobar are not "the same with same addresses" since the return addresses are different and the argument values are different.  All that is likely to be the same for the call frames is the stack pointer and the link to the previous frame.  

Many more call frames are created on the main stack than the three you mention.  Foobar calls printf, which creates a call frame, and printf calls a host of other functions, all of which have call frames. Pthread_create calls create other call frames.  

The size of stacks is a system configurable value.  On Linux (at least on Fedora) it is 10Mb, not 2Mb.  
0
 
phoffricCommented:
>> The frames created for the calls to foobar are not "the same with same addresses"
>> In both of these foobar call frames, the call frame is the same with same addresses
I think you are saying that the values in foobar's callframe are different (e.g., the arguments, the return address). But that doesn't say that the addresses of foobar's call frame is different in this scenario. (They don't have to be the same; but they are in this particular scenario.)

printf indeed does result in its call frame. And that omission was due to the fact that I just put printf in as debug to illustrate what the argument's addresses were.
0
 
phoffricCommented:
>> The size of stacks is a system configurable value.  On Linux (at least on Fedora) it is 10Mb, not 2Mb.

I was just making an illustration of this particular Cygwin configuration. There's nothing in the C++ spec about this size, so it is implementation dependent (and as you say, configurable).
0
 
sukhoi35Author Commented:
Hello Experts,
I had limited access to internet the last few days and hence could not respond to your comments. I will act soon.

regards.
0
 
sukhoi35Author Commented:
Infinity08>>> "could you clarify the question, please ? Were you actually talking about the call stack"

I was actually a little confused when I was reading Section 2 of page 15 at the link:
http://cslibrary.stanford.edu/102/PointersAndMemory.pdf

Hence this question :)


Reading all your comments did give me a better understanding of threads in a single-threaded environment. For multi-threads, this is my understanding

1) if main() spawns 2 threads, I will be adding two new frames for each of the threads in main's call-stack.
2) then create new call stack for each of the new threads and add new frames to the respective call-stack when funtions are called.

I am sorry if I have understood the above discussion wrong, but please correct me if I am wrong.
0
 
Infinity08Connect With a Mentor Commented:
There are no stack frames added to the main stack when starting a new thread. At least not in the way that you seem to understand it.

The thread was most likely created by calling a function (like pthread_create), and this function call indeed causes the creation of a new stack frame on the main call stack, but that's not different than what's done for any other function call. After the function returns, the stack frame is removed from the call stack, just like for any other function.
Or in other words : this stack frame has nothing to do with the created thread, and will not exist for the entire lifetime of the thread.

Each thread gets its own call stack. And each function call made in the thread will cause the creation of a stack frame on the thread call stack. Just like for any other function call.
0
 
sukhoi35Author Commented:
Thanks for all your responses, I feel it is time now for me to close this question
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.