[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

What is a call stack?

Posted on 2011-05-06
17
Medium Priority
?
482 Views
Last Modified: 2012-05-11
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.
0
Comment
Question by:sukhoi35
  • 6
  • 5
  • 4
  • +1
17 Comments
 
LVL 32

Expert Comment

by:phoffric
ID: 35706033
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
 
LVL 32

Expert Comment

by:phoffric
ID: 35706105
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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 600 total points
ID: 35706314
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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

by:sukhoi35
ID: 35712164


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
 
LVL 53

Expert Comment

by:Infinity08
ID: 35712515
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
 
LVL 8

Accepted Solution

by:
eager earned 800 total points
ID: 35712814
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 35712875
@eager : I think you'll find that your post doesn't add much to what I already posted ;)
0
 
LVL 32

Assisted Solution

by:phoffric
phoffric earned 600 total points
ID: 35714332
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 35714378
>> 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
 
LVL 32

Expert Comment

by:phoffric
ID: 35714390
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
 
LVL 8

Assisted Solution

by:eager
eager earned 800 total points
ID: 35714537
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
 
LVL 32

Expert Comment

by:phoffric
ID: 35714609
>> 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
 
LVL 32

Expert Comment

by:phoffric
ID: 35714612
>> 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
 

Author Comment

by:sukhoi35
ID: 35788616
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
 

Author Comment

by:sukhoi35
ID: 35807928
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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 600 total points
ID: 35808091
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
 

Author Closing Comment

by:sukhoi35
ID: 35808205
Thanks for all your responses, I feel it is time now for me to close this question
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Today, the web development industry is booming, and many people consider it to be their vocation. The question you may be asking yourself is – how do I become a web developer?
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
Six Sigma Control Plans
Progress

834 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question