How is the bottom of stack determined?

Question

A stack is a contiguous block of memory containing data. A register called the stack pointer (SP) points to the top of the stack. The bottom of the stack is at a fixed address.

How is the stack bottom fixed by the kernel?

Answer 1

That would be part of the implementation of the stack itself. If you're implementing a stack in (for example) C, you may store the stack pointer and the current number of elements. Or the stack pointer along with the base of the stack, something like:

typedef struct {
    int *sp_empty;
    int *sp;
    int *sp_full;
} tIntStack;

tIntStack stk;

// Initialise 20-element stack.
stk.sp = stk.sp_empty = malloc (sizeof(int) * 20);
stk.sp_full = &(stack[20]);

// Push a value x, detecting overflow.    
if (stk.sp == stk.sp_full) { error here}
*(stk.sp) = x;
stk.sp++;

// Pop a value x, detecting underflow.    
if (stk.sp == stk.sp_empty) { error here}
stk.sp--;
x = *(stk.sp);

If you're talking about a CPU stack (return addresses and so forth), you may detect the stack underflow by virtue of the fact that you crash. Badly.

---

As an example, in olden days when processors were limited to 64K address space, CPUs typically tested memory until they found the first byte that didn't read the same as what was just written (in the boot up process). The was the first byte beyond actual physical memory so they set SP to one below that. Of course, some (small number of) machines had 64K of physical RAM so just set SP to the top of the address space.

The process nowadays, in huge-address-space, virtual-memory, multi-tasking operating systems, is a little more complicated but it still boils down to (in most cases):

• Address space is allocated for a process.
• SP is set to somewhere in that address space.
• Process runs.

At that point, you're probably on your own as far as the kernel is concerned. It's responsibility stops at the point where your code starts running other than task switching and providing services as requested, but that's nothing to do with your stack. If your buggy code overflows or underflows the stack, that's your problem.

The kernel may check your SP on task switch to see if you've done something wrong but that's by no means guaranteed. It may also use hardware memory protection to detect an underflow (if the stack is at the top of your allocated address space). But again, this depends entirely on the kernel you're using.

Answer 2

I typed out a longer answer, but it rambled, so here's a shorter one...

When a process is started, it needs a stack for the purpose of storing temporary values (i.e. automatic allocation) or stack frames when functions are called. The memory for this stack has to come from somewhere.

So what the OS does is create a mapping in virtual memory for the stack, and assign the stack pointer to the high address of this block. In a predecrement stack, where the stack pointer is decremented prior to dereferencing, the initial stack pointer is actually the address past the last address in the mapped space.

When the process tries to put something on the stack, it results in an access to this memory region, which doesn't have any physical RAM mapped to it. This causes a page fault, which results in the OS kicking the least-used (or close to it) page of RAM into the swap drive or page file, and reassigning the physical RAM page to the stack page being accessed. Now that there's physical RAM, the OS returns and the process continues, putting the pushed data into the stack memory.

So what happens if you pop everything off the stack and then try to pop again? That last pop, where the stack pointer is at its initial value, results in an access to a virtual memory address that's not mapped to the stack. This causes a segmentation fault, which means the process tried to access memory it never allocated. The OS responds by terminating the process and cleaning up whatever it can.

Why not map a page past the end of the stack? because that would result in reading uninitialized RAM, which will contain whatever used to be using that page of physical RAM. There is simply no way this can produce a correctly-functioning program (to say nothing of how this is a huge security risk), so it is still best to kill the program.

Answer 3

I assume that you mean "fixed in the memory space of the process", and not "fixed in the overall memory". You can look at where the stack bottom is in any recent Linux system by searching for a line like

bfbce000-bfbe3000 rw-p bffeb000 00:00 0          [stack]

in the output of cat /proc/<pid-here>/maps. The bottom of the stack is, in this case, at 0xbffeb000. In my system, all stack bottoms seem to fall in one of bffca000 bffcb000 bffdd000 bffe0000 bffe4000 bffe6000 bffeb000 (after looping through ~200 processes).

I guess that these values are assigned deep in the kernel, wherever processes are first created.