What determines the size space for the heap and the stack?

[Lost In Cyberia]

Hey everyone, hopefully this is the right area to post. I was poking around in my /proc directory tonight, and began thinking. (Usually this leads to massive amounts of questions). When a program is executed, how does the OS know how much total memory to give to the program? And is the the total memory even divided 50/50 for it's heap and stack? What determines rather the application have more stack memory or more heap memory?

I'm sure this is answered somewhere, but I can't get a clear answer, thanks in advance!

[cooper]

Start reading here.
(What comes next is from what I remember from my school days. It's been a while so I might be off)
If you look at this little bit of C code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    char buffer[40] = "Hello world.\n";
    char *bufcopyPtr;
    bufcopyPtr = (char*)malloc(sizeof(char)*strlen(buffer));
    if (bufcopyPtr == NULL) {
        printf("Memory allocation error.\n");
    } else {
        strncpy(bufcopyPtr, buffer, strlen(buffer));
        printf("%s", bufcopyPtr);
        free(bufcopyPtr);
    }
}

All memory claimed using malloc and returned with free is allocated on the heap, which is basically just general memory made available to your program by the OS in response to your program's explicit requests. The other stuff like that fixed buffer goes onto the stack. The main feature of things that go onto the stack is that their size is known up front. That buffer variable will always claim 40 bytes, regardless of what you do with it. The size of that bufcopyPtr variable on the other hand isn't known until the program is running. Sure, in this case the compiler could work it out but code is rarely this simple.

Because the stack also contains function state (when the strlen function is invoked, the stack will hold somewhere where in memory the currently executing instruction was) if you managed to write more than the allotted amount of bytes to something on the stack, you can divert program execution to somewhere else. This is what you try to achieve when you inject shellcode - overwrite that chunk of the stack containing the return pointer such that when the current function does return it actually invokes a different function (evecve with the path to the shell as parameter, say).

So you might say "well, why use that stack in the first place then? Let's just use the heap for everything." The reason is because the stack is faster. The program can address the bytes in buffer directly whereas for the bufcopyPtr it first needs to go to the address in memory that this pointer references and only then access the relevant bits.

There is no even devision between stack and heap. When you start a program you get a virtual address space from, say, 0x00000000 to 0xFFFFFFFF. Stack starts at 0x00000000 and grows up. Heap starts at 0xFFFFFFFF and grows down. They could meet in the middle, but by then you'll probably get an error from the OS saying it's out of memory, either when you malloc or when you try to invoke a function and it can't find the memory to create the new stack frame.

[Lost In Cyberia]

First of all, I want to say thanks Cooper. You always seem to give a detailed and thought out answer to my questions. I really appreciate it...

Moving onto my question, http://en.wikipedia.org/wiki/Virtual_address_space This actually was what I was digging for more though. I may have worded my question poorly.

The article here says on a 32 bit Windows machine, a program or process is always given 4 gigs of Virtual address space, and By default, 64-bit processes have 8TB of virtual address space. So this is going to sound silly, but obviously no machine has anywhere near that. So why even give programmers the option of using that much? If your average user has let's say 16 gigs of RAM, isn't this just asking for trouble? The programmer coud write something that takes up far more than 16gigs, and the program when executed will think everything is OK, because it 'see's 8TB's of available address space?

Do I have this wrong?

[cooper]

The article here says on a 32 bit Windows machine, a program or process is always given 4 gigs of Virtual address space, and By default, 64-bit processes have 8TB of virtual address space. So this is going to sound silly, but obviously no machine has anywhere near that.

Heh. You'd be surprised. Granted, it won't be the one under your desk.

One of our customers is running our software on a HP Superdome. When you're thinking about hacking the Gibson, something like this should come to mind.

Also, there's nothing stopping you from buying a few terabytes of diskspace and setting that up as swap space. Granted, it'll take a while for you to fill that up, but the point is that if you want to do that, you can.

So why even give programmers the option of using that much? If your average user has let's say 16 gigs of RAM, isn't this just asking for trouble? The programmer coud write something that takes up far more than 16gigs, and the program when executed will think everything is OK, because it 'see's 8TB's of available address space?

Do I have this wrong?

Yes, you do. The point is that your program assumes it's in a brewery and it can drink all the beer in the world and then some since they can always make more. What the program doesn't know is that the brewery is just a facade (virtual address space after all) and the OS has only a few crates of beer on stand-by and each time the program demands another, he gets a bottle from one of those crates. The beer itself is actually brewed abroad these days. When the crates are all empty, the program is still going to be told there's no more beer.

The fact of the matter is that while most programs don't need anywhere near that much memory, some very specific ones do (or might). Since there's no real reason to want to limit the program, why bother with doing so in the first place?

[Sitwon]

To slightly extend Cooper's explanation.

1. Don't forget about swap space. Even if you have only 16GB of physical RAM, you could extend that (as far at the running program is concerned) by periodically swapping inactive pages of memory to disk. There is, of course, a performance penalty, but for some applications it's worth it.

2. The way virtual address space works is that your program doesn't access the RAM directly, rather it makes system calls and tells your Operating System's kernel to do it. That's how each application can think it has it's own 8TB even though your system doesn't actually have that much space. The virtual address space of a given process doesn't even have to be contiguous. When your application requests more memory and the OS determines that there is none left to allocated, there OS can generally do one of two things: a) It could terminate the application with an out-of-memory error, or b) it could simply block until the requested memory is available.

[cooper]

When your application requests more memory and the OS determines that there is none left to allocated, there OS can generally do one of two things:

a) It could terminate the application with an out-of-memory error, or

b) it could simply block until the requested memory is available.

c) simply deny the request and let malloc() return NULL. Which is the 'natural' way of things.

The Linux kernel has an OOM Killer (Out Of Memory Killer) that does a) for a somewhat random process when it runs out of memory. Complex heuristics are at play to discover how to best save the system from itself. It could mean it kills your browser process because your video player is running out of memory but is in fact the process you're actively using. It could've killed the video player process just as easily though. I run into the bugger every so often when playing with my ARM machines because they have so (relatively) little memory to begin with.

[Lost In Cyberia]

heh, ok cheers to both of you, that all makes sense... Last question for now... If two processes are running concurrently, is there any way for one process to get "priority" (first dibs if you will), on memory? Let's say both are memory hogs and are requesting more and more, from a programmers point of view can you do anything to have your program take priority to avoid running out of memory first?

[cooper]

I'd guess one such strategy would be to claim all the memory you expect to need early on. You'd have to write to that memory to actually claim it though, since the memory page isn't actually assigned until you do. One problem is that you can't really tell when the system is out of memory. Your program would have to monitor the memory use of the system to see if it overstepped its boundary. Otherwise the only clue it gets that it's gone too far is the gentile push of a SIGKILL.

Once the OOM Killer comes into play, the memory use of all processes is considered. The amount actually used (as opposed to claimed. See previous remark about writing to the memory) is used as a factor to determine if this is the program that should die. Programs running as root get a small reduction in their score on the assumption that those programs are more important than regular programs. The other thing that can be used to influence the OOM killer is to change the value of the oom_score_adj file for the process under /proc. If you write the value -1000 to that file, it becomes immune to the OOM Killer. You'd have to be root to write to the file though. Also note that if the OOM can't kill your process, it has to kill something else. If that something the init process, that means your system will reboot.

[Lost In Cyberia]

Ha, my first time hearing about the OOM killer. Is it a process itself? Does it work before resorting to using Swap space, or is it the very last ditch effort to recover address space, even after Swap has been given out?

[cooper]

The nitty gritty.

It's a kernel function that responds to the system being unable to cope with the demands of the processes it's got running.

Initially, the process that's requesting memory using one of the *alloc C functions is being returned null. Not one to take a hint, the program simply retries. When this happens often enough and in close succession, the kernel decides something needs to be done so it starts the OOM Killer and finds a suitable lamb for the slaughter.

Things can be subtle though. Imagine for a moment if you will some administrator with more system privs than brains deciding to put a swap file on a mounted Samba share. When memory needs to move to swap to make room for something else, that causes all sorts of kernel activity to get that data moved across the network and into the swap file. This activity needs (wait for it) memory allocations to succeed so that the data to move can be placed into a network transaction buffer, cut up into packets, checksums calculated. And that's still discounting the overhead of using Samba in the first place. So you're low on memory and the only way to make room is by requiring additional memory. All the kernel can do in such a case is kill off a process or two to make some room. Similarly, the XFS filesystem (if memory serves) has, relative to for instance ext2, quite a lot of overhead. If your swapfile resides there, something not unlike what I just described is again liable to take place. There was an article about it on LWN a few years back.

Some reading on the subject.

Edited January 22, 2015 by Cooper