By Garrick


2016-11-01 18:20:14 8 Comments

I am reading about memory allocation and activation records. I am having some doubts. Can anyone make the following crystal clear ?

A). My first doubt is that "Are activation records created on stack or heap in C" ?

B). These are few lines from an abstract which i am referring :-->

Even though memory on stack area is created during run time- the amount of memory (activation record size) is determined at compile time. Static and global memory area is compile time determined and this is part of the binary. At run time, we cannot change this. Only memory area freely available for the process to change during runtime is heap.At compile time compiler only reserves the stack space for activation record. This gets used (allocated on actual memory) only during program run. Only DATA segment part of the program like static variables, string literals etc. are allocated during compile time. For heap area, how much memory to be allocated is also determined at run time.

Can anyone please elaborate these lines as i am unable to understand anything ? I am sure the explaination would be of great need to me.

3 comments

@Basile Starynkevitch 2016-11-01 18:50:08

In theory, a C99 (or C11) compatible implementation (e.g. a C compiler & C standard library implementation) do not even need (in all cases) a call stack. For example, one could imagine a whole program compiler (notably for freestanding C implementation) which would analyze the entire program and decide that stack frames are unneeded (e.g. each local variable could be allocated statically, or fit in a register). Or one could imagine an implementation allocating the call frames as continuation frames (perhaps after CPS transformation by the compiler) elsewhere (e.g. in some "heap"), using techniques similar to those described in Appel old book Compiling with Continuations (describing an SML/NJ compiler).

(remember that a programming language is a specification -not some software-, often written in English, perhaps with additional formalization, in some technical report or standard document. AFAIK, the C99 or C11 standards do not even mention any stack or activation record. But in practice, most C implementations are made of a compiler and a standard library implementation.)

In practice, allocation records are call frames (for C, they are synonyms; things are more complex with nested functions) and are allocated on a hardware assisted call stack on all reasonable C implementations I know. on Z/Architecture there is no hardware stack pointer register, so it is a convention (dedicating some register to play the role of the stack pointer).

So look first at call stack wikipage. It has a nice picture worth many words.

Are activation records created on stack or heap

In practice, they (activation records) are call frames on the call stack (allocated following calling conventions and ABIs). Of course the layout, slot usage, and size of a call frame is computed at compile-time by the compiler.

In practice, a local variable may correspond to some slot inside the call frame. But sometimes, the compiler would keep it only in a register, or reuse the same slot (which has a fixed offset in the call frame) for various usages, e.g. for several local variables in different blocks, etc.

But most C compilers are optimizing compilers. They are able to inline a function, or sometimes make a tail call to it (then the caller's call frame is reused as or overwritten by the callee call frame), so details are more complex.

See also this How was C ported to architectures that had no hardware stack? question on retro.

@Garrick 2016-11-01 18:52:23

Can you please tell the difference between defined and allocated .ie. memory is determined/defined at compile time but allocated at run time?

@Michael Dorgan 2016-11-01 18:52:43

Congrats, you quoted the standard. Now, lets teach with something that he might be able to understand...

@Basile Starynkevitch 2016-11-02 08:45:57

@MichaelDorgan: Where did I quote the standard? I did not even look into it to answer (and no, I don't know it by heart)... And I did take care to give useful hyperlinks.

@Björn Lindqvist 2016-11-01 20:20:23

In C (given how it is almost universally implemented*) An activation record is exactly the same thing as a stack frame which is the same thing as a call frame. They are always created on the stack.

The stack segment is a memory area the process gets "for free" from the OS when it created. It does not need to malloc or free it. On x86, a machine register (e.g RSP) points to the end of the segment and stack frames/activation records/call frames are "allocated" by decrementing the pointer in that register by how many byte to allocate. E.g:

int my_func() {
    int x = 123;
    int y = 234;
    int z = 345;
    ...
    return 1;
}

An unoptimizing C compiler could generate assembly code for keeping those three variables in the stack frame like this:

my_func:
    ; "allocate" 24 bytes of stack space
    sub  rsp, 24     
    ; Initialize the allocated stack memory
    mov  [rsp], 345      ; z = 345
    mov  [rsp+8], 234    ; y = 234
    mov  [rsp+16], 134   ; x = 123
    ...
    ; "free" the allocated stack space
    add  rsp, 24
    ; return 1
    mov  rax, 1
    ret
  • In other contexts and languages activation records can be implemented differently. For example using linked lists. But as the language is C and the context is low-level programming I don't think it is useful to discuss that.

@Michael Dorgan 2016-11-01 18:32:58

As a quick answer, I don't even really know what an activation record is. The rest of the quote has very poor English and is quite misleading.

Honestly, the abstract is talking about absolutes when in reality, there really are not at all absolute. You do define a main stack at compile time, yes (though you can create many stacks at runtime as well).

Yes, when you want to allocate memory, one usually creates a pointer to store that information, but where you place that is completely up to you. It can be stack, it can be global memory, it can be in the heap from another allocation, or you can just leak memory and not store it anywhere it all if you wish. Perhaps this is what is meant by an activation record?

Or perhaps, it means that when dynamic memory is created, somewhere in memory, there has to be some sort of information that keeps track of used and unused memory. For many allocators, this is a list of pointers stored somewhere in the allocated memory, though others store it in a different piece of memory and some could even place that on the stack. It all depends on the needs of the memory system.

Finally, where dynamic memory is allocated from can vary as well. It can come from a call to the OS, though in some cases, it can also just be overlayed onto existing global (or even stack) memory - which is not uncommon in embedded programming.

As you can see, this abstract is not even close to what dynamic memory represents.


Additional info:

Many are jumping all over me stating that 'C' has no stack in the standard. Correct. That said, how many people have truly coded in C without one? I'll leave that alone for now.

Defined memory, as you call it, is anything declared with the 'static' keyword within a function or any variable declared outside of a function without the 'extern' keyword in front of it. This is memory that the compiler knows about and can reserve space for without any additional help.

Allocated memory - is not a good term as defined memory can also be considered allocated. Instead, use the term dynamic memory. This is memory that you allocate from a heap at run-time. An example:

char *foo;
int my_value;

int main(void)
{
    foo = malloc(10 * sizeof(char));
    // Do stuff with foo
    free(foo);
    return 0;
}

foo is "defined" as you say as a pointer. If nothing else were done, it would only reserve that much memory, but when the malloc is reached in main(), it now points to at least 10 bytes of dynamic memory as well. Once the free is reached, that memory is now made available to the program for other uses. It's allocated size is 'dynamic'. Compare that to my_value which will always be the size of an int and nothing else.

@Garrick 2016-11-01 18:44:56

Static and global variables are known at compile time, right ?

@Michael Dorgan 2016-11-01 18:45:56

That is correct. The main stack is usually defined at compile time as well.

@too honest for this site 2016-11-01 18:46:45

There is no stack in the C language! It is an implementation detail and not required. I don't see this answers the question ("explain this excerpt"), not that the question can be answered by anyone else than the original author.

@pm100 2016-11-01 18:47:41

how is the stack defined at compile time? If I recurse based on user input I have a deeper stack depending on what was input. The stack is a dynamic resource (with perhaps OS defined upper limit)

@too honest for this site 2016-11-01 18:48:02

@Willturner: There are no distinct "global" variables! Just static variables. How about reading the standard instead of obscure resources?

@Michael Dorgan 2016-11-01 18:48:08

@Olaf, I am trying to teach here. Yes, you are 100% correct to the detail that there is indeed no "stack" defined by 'C', but we both know that 99.999999% of programs use one, so let it go.

@Garrick 2016-11-01 18:48:46

@MichaelDorgan, Can you please tell the difference between defined and allocated .ie. memory is determined/defined at compile time but allocated at run time .

@too honest for this site 2016-11-01 19:03:52

@MichaelDorgan: That's actually the point. We are a Q&A, not a tutoring site.

@Michael Dorgan 2016-11-01 19:06:22

Ok, he asked a question, I answered it in a way that he will hopefully understand. If the question were that bad, it would have been down-voted to obscurity and closed in minutes. It was not. Someone with 20x my rep came in and answered it with the standard as well. Hopefully between the 2 of us, good will have been done today.

Related Questions

Sponsored Content

55 Answered Questions

[SOLVED] How to create a memory leak in Java

13 Answered Questions

[SOLVED] What does "Memory allocated at compile time" really mean?

3 Answered Questions

[SOLVED] Stack Memory vs Heap Memory

  • 2011-04-29 19:09:02
  • Steveng
  • 122031 View
  • 89 Score
  • 3 Answer
  • Tags:   c++ memory

10 Answered Questions

[SOLVED] Improve INSERT-per-second performance of SQLite?

25 Answered Questions

[SOLVED] Could not reserve enough space for object heap

  • 2010-12-09 17:46:37
  • Narendra
  • 903873 View
  • 263 Score
  • 25 Answer
  • Tags:   java jvm heap

23 Answered Questions

[SOLVED] Which is faster: Stack allocation or Heap allocation

25 Answered Questions

[SOLVED] What and where are the stack and heap?

17 Answered Questions

[SOLVED] What REALLY happens when you don't free after malloc?

  • 2009-03-17 15:29:09
  • Scott
  • 106624 View
  • 517 Score
  • 17 Answer
  • Tags:   c malloc free

5 Answered Questions

[SOLVED] Program stack and heap, how do they work?

  • 2010-01-14 19:52:44
  • Boolean
  • 18716 View
  • 27 Score
  • 5 Answer
  • Tags:   stack kernel heap

3 Answered Questions

[SOLVED] static objects vs. stack- & heap- based objects

  • 2011-06-26 10:29:53
  • Joshua
  • 1562 View
  • 0 Score
  • 3 Answer
  • Tags:   static stack heap

Sponsored Content