25

How does the compiler enforce the stack memory to be contiguous, does it cause the memory to be moved everytime while the program is running or does it reserve the memory on stack needed by program before running it?

7
  • Which operating system? C++ has no "stack memory".
    – GManNickG
    Feb 23, 2011 at 3:34
  • Windows. but how can it work without stack memory?
    – user2133
    Feb 23, 2011 at 3:37
  • @user: Everything could be dynamically allocated.
    – GManNickG
    Feb 23, 2011 at 3:57
  • Are we talking about "heap memory"?
    – user2133
    Feb 23, 2011 at 4:23
  • Why should the stack be contiguous. There is no requirement in the language OS or the hardware for this stifling restriction. Feb 23, 2011 at 5:58

3 Answers 3

32

The stack for a given thread is often contiguous in virtual memory (on Linux and similar systems, and in user mode in Windows). The Windows kernel (in Windows Vista and above) and z/OS allow discontiguous stacks in virtual memory, and GCC 4.6 will also allow that. The compiler does not need to move the stack around at all, even for the systems that have discontiguous virtual addresses for the stack; they just change where new parts are allocated. The operating system might remap physical pages to virtual ones so that the stack may not be contiguous in physical memory, though, even if it is in virtual memory.

22
10

There are no requirements for the stack to be contiguous in the language the OS or the hardware.

I challenge anybody to site a reference that explicitly says this is a requirement.

Now a lot of implementations do use contiguous memory because it is simple. This is also how the stack concept is taught to CS students (Stack grows down heap expands up). But there is no requirements to do this. I believe that MS even experimented with placing stack frames in random locations in the heap to prevent attacks the used deliberate stack smashing techniques.

The only requirement of the stack is that frames are linked. Thus allowing the stack to push/pop frames as scopes are entered/left.

But this all orthogonal to the original question.

The compiler does not try and force the stack to be in contiguous memory. There is no requirements at the language level that require the stack to be contiguous.

How is the stack usually implemented.

If this was the question. Then you would get a more detailed and accurate answer from the community.

11
  • 1
    I challenge anybody to site a reference that explicitly says this is a requirement.... well, I challenge you to provide an example of how this could work, for example, on a Windows x86 system. :)
    – user541686
    Feb 23, 2011 at 6:58
  • 1
    @Mehrdad: If you read carefully I have already explained how. Each stack frame just requires a pointer back to the previous stack frame. Popping the stack frame is a matter of resetting the stack pointer with the pointer of the previous stack frame (which is held in the current stack frame.In exactly the same manor as if the stack frame where in contiguous space). There is no change in implementation weather the stack is in contiguous space or spread though the heap. Some CPU have special instructions to push/pop the stack frame and move the SP all in one instruction so more work is required. Feb 23, 2011 at 8:07
  • 2
    @Mehrdad: Read more carefully. There is no OS limitation that requires a contiguous stack. Though an OS vendor implementation may limit its implementation to a contiguous stack for any number of reasons (including but not limited to efficiency). Feb 23, 2011 at 8:23
  • 1
    @Mehrdad: could you replace your sentences with "Windows". No. I am trying to be very specific about what I say not matter your twisting of the subject. You miss the point again. Vendor specific implementations of an OS can apply arbitrary restrictions on their usage (such as windows may impose contiguous memory requirements on a stack (I suppose)). But there are no OS limitations that require a contiguous stack. Feb 23, 2011 at 9:01
  • 1
    @Mehrdad: Maybe not what you wanted. But I never mentioned a specific OS for a very good reason. I said there is no requirements for an organism to breath air. You said show me a human that does not need to breath air. :-) It would be pointless to argue that point. Feb 23, 2011 at 9:48
4

You have your memory address space, let's say it runs from 1 to 100. You allocate your stack from 1 upwards and you allocate your heap from 100 downwards. Ok so far?

Due to the very nature of the stack it's always compact (has no holes). That happens because everything that's in the stack is the context of some function that was called. Whenever a function exits, its context is removed from the top of the stack and we fall back to the previous function. I think you can understand it well if you get a debugger and just follow the function calls while keeping in mind how the stack must be.

Heap, on the other hand is not so well behaved, let's say that we have reserved memory from 70 to 100 for heap. We may allocate a block of 4 bytes there and it might go from 70 to 74 then we allocate 4 bytes more and now we have memory allocated from 70 to 78. But that memory may be deallocated at any point of the program. So you might deallocate the 4 bytes you allocated at the beginning, thus creating a hole.

That's how things happen in you address space. There's a table that the kernel keeps that maps pages from the address space to pages in real memory. As you probably have noticed, you can't hope to have all everything set up that nicely when you have more than one program running. So what kernel does is make each process think the whole address space is contiguous memory (let's not think about memory mapped devices for now), even though it might be mapped non-contiguously in memory.

I hope to have given a reasonable overview on the subject, but there are probably better authors than me, that you'll probably enjoy reading much more. So look for texts on virtual memory, it might be a nice starting point for you to understand what you want. There are several books that will describe it in greater or lesser detail. A few that I know of: Structured computer organization, by tanenbaum; Operating System Concept, by Silberschatz. I'm pretty sure Knuth discusses it in his algorithm books as well. If you feel adventurous, you might try reading x86 implementation of it on intel manuals.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.