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?

Noob Saibot
  • 4,573
  • 10
  • 36
  • 60
user2133
  • 253
  • 3
  • 6

3 Answers3

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.

Jeremiah Willcock
  • 30,161
  • 7
  • 76
  • 78
  • @Jeremiah: "Almost always" is interesting... know of any other examples? – user541686 Feb 23 '11 at 03:10
  • 2
    @Merhdad: I believe there is a trick for moving parts of the stack if you are very careful. GCC 4.6 is claimed to be able to do it: http://gcc.gnu.org/wiki/SplitStacks. – Jeremiah Willcock Feb 23 '11 at 03:12
  • @Jeremiah: +1 That link is definitely enlightning... however, is the stack for a **single thread** discontiguous? It seems to me that they're making multiple threads... – user541686 Feb 23 '11 at 03:15
  • 1
    @Mehrdad: They are talking about each thread's stack being discontiguous (possibly) to allow it to be dynamically resized. – Jeremiah Willcock Feb 23 '11 at 03:17
  • @Jeremiah: Huh, very interesting... I learned something new today. :D – user541686 Feb 23 '11 at 03:19
  • There is absolutely no need to have a contiguous stack. This is just bumkum (In CS school the stack is tough as a contiguous chunk of memory as it simplifies the concept for students (and a lot of implementations may have contiguous stacks)). But there is absolutely no requirement or need for it. – Martin York Feb 23 '11 at 06:01
  • @Martin: Sometimes it is a requirement, sometimes it isn't -- "there is absolutely no requirement" is incorrect, because in Windows, there's no way to extend the stack other than [by triggering a (contiguous) guard page](http://support.microsoft.com/kb/100775). This idea of a discontiguous stack was new to me because it's on Linux, but as far as I know, it's not possible in Windows. – user541686 Feb 23 '11 at 06:20
  • @Mehrdad: Did you see something in the linked GCC document that was specific to Linux? GCC is cross-platform, and as far as I can see the described techniques are equally applicable to builds for Windows.... – Tony Delroy Feb 23 '11 at 06:53
  • @Tony: Yeah, in the second paragraph: `This is currently implemented for 32-bit and 64-bit x86 targets running GNU/Linux in gcc 4.6.0 and later.` Also, did you see the link I posted? I don't see how Windows could possibly support discontiguous stacks. – user541686 Feb 23 '11 at 06:54
  • @Mehrdad: 4.6 is the current non-stable dev build... that it's currently implemented for one target doesn't mean there's anything platform-specific in the technique. The link you posted talks about what the MS Visual C++ compiler *is* doing, which is irrelevant to what it could do, or what GCC probably will do. – Tony Delroy Feb 23 '11 at 06:59
  • @Mehrdad: This page (http://social.msdn.microsoft.com/Forums/en-US/wdk/thread/297ed7a3-d69f-47ec-ba64-5d8839cdfae5/) suggests that Windows uses discontiguous stacks sometimes, too, at least in the kernel. – Jeremiah Willcock Feb 23 '11 at 06:59
  • @Tony: This is an OS issue, not a compiler issue... the compiler is doing what it's doing because of OS restrictions. @Jeremiah: After reading that, I think I honestly don't know enough about the kernel to judge what they meant by "discontiguous 16KB chunks", but I'm just failing to see how that would work in user-mode. If a Windows function executed `push` and then overflowed the current portion of the stack, how could the program possibly redirect it somewhere else? It's not like it can trap guard pages without OS support... – user541686 Feb 23 '11 at 07:04
  • @Merhdad, @Martin: z/OS apparently uses discontiguous stacks for user code: http://publib.boulder.ibm.com/infocenter/zos/v1r9/index.jsp?topic=/com.ibm.zos.r9.ceev100/stkfrmap.htm. I guess we can't really say anything absolute about the stack being contiguous. – Jeremiah Willcock Feb 23 '11 at 07:05
  • @Mehrdad: On Windows, the OS automatically traps stack overflows (and users can be notified about them), so it could add more chunks to the stack if needed. See the z/OS link to find out how the growth is actually implemented (I imagine Windows is using a similar mechanism). – Jeremiah Willcock Feb 23 '11 at 07:07
  • @Jeremiah: I *do* know that the OS traps stack overflows (that's why the use a guard page), but I do *not* think that the user can be notified about them... by what mechanism is this done? I don't believe there's any user-mode callback in Windows that gets called on a guard page trap. – user541686 Feb 23 '11 at 07:13
  • 1
    @Mehrdad: see http://msdn.microsoft.com/en-us/library/89f73td2%28v=vs.80%29.aspx for a sample program. – Jeremiah Willcock Feb 23 '11 at 07:15
  • @Mehrdad, @Martin, @Tony: I rewrote a bunch of my answer based on the research triggered by the comments; see if the new version is more accurate. – Jeremiah Willcock Feb 23 '11 at 07:16
  • @Jeremiah: The link says that `When the code causes the stack pointer to point to an address on this page, an exception occurs and the system [...] allocates a new guard page that is located one page below the last one.` So doesn't that mean it's contiguous? – user541686 Feb 23 '11 at 07:20
  • @Mehrdad: Which link? The one about trapping overflows in user mode does suggest that the stack is contiguous; it's the link about the kernel that says the behavior is different there. – Jeremiah Willcock Feb 23 '11 at 07:21
  • @Jeremiah: Yeah, I meant the user-mode one. I honestly don't see what they meant about the kernel-mode one... I'm looking at ReactOS, and so far, I haven't seen any trace of discontiguous stacks (although that's neither proof nor disproof of anything, since ReactOS != Windows). – user541686 Feb 23 '11 at 07:25
  • 1
    @Mehrdad: Look at page 7 of http://download.microsoft.com/download/9/c/5/9c5b2167-8017-4bae-9fde-d599bac8184a/MemMgt.docx – Jeremiah Willcock Feb 23 '11 at 07:35
  • Wow... I'd never heard of it. It seems to be a kernel-mode-only feature. I stand corrected. :) – user541686 Feb 23 '11 at 07:55
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.

Community
  • 1
  • 1
Martin York
  • 257,169
  • 86
  • 333
  • 562
  • 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 '11 at 06: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. – Martin York Feb 23 '11 at 08:07
  • @Martin: I'm not talking about how the stack could be implemented from scratch; I'm talking about how it could be done on Windows, since the OS is the ultimate controller of the stack, not the user-mode code. We just had a [discussion on this](http://stackoverflow.com/questions/5086577/is-stack-memory-contiguous/5086592#5086592) (in case you didn't see it already), and it seems to be consistent with the fact that the OS is capable of doing this, but user-mode code doesn't seem to be able to. – user541686 Feb 23 '11 at 08:14
  • 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). – Martin York Feb 23 '11 at 08:23
  • @Martin: Instead of saying "OS" could you replace your sentences with "Windows"? My initial comment was on Windows, and you're consistently using the (relatively abstract) word "OS", with no concrete ideas. Again, this issue was already discussed on a different post, and it seems that it's not possible in user-mode Windows code, though feel free to correct us if you find specific evidence to the contrary. – user541686 Feb 23 '11 at 08:31
  • 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. – Martin York Feb 23 '11 at 09:01
  • @Martin: You're missing *my* point. My original comment was on Windows, but *you're* twisting the subject and talking about general issues that I wasn't talking about. :( – user541686 Feb 23 '11 at 09:14
  • 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. – Martin York Feb 23 '11 at 09:48
  • @Martin: But the way you're reasoning it, you could also argue (with varying levels of difficulty) that a stack doesn't even have to exist, that the modern concept of a computer doesn't even have to be what it is, that RAM doesn't even have to exist, etc... they might be valid points, but for practical purposes, they aren't exactly useful in answering a not-so-much-out-of-the-ordinary question. – user541686 Feb 23 '11 at 10:30
  • @Mehrdad: Yes. There is no reason to have a stack as described in your CS class. The stack can just as easily be implemented as part of the heap. – Martin York Feb 23 '11 at 16:03
  • @ Mehrdad: Taking things to the extreme! You do not even need the concept of a stack. The Russians were very good in the 60/70 at developing OS and compilers that did not use a stack at all. There compilers generated self modifying code to provide the same functionality. (Vey/very interesting concept). Ultimately they switched to the western technique of using stacks. BUT; take a second and think about that. Their space systems in the early days were built with computers that used self modifying code! – Martin York Feb 23 '11 at 16:05
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.

Rafael Almeida
  • 2,377
  • 3
  • 22
  • 32