Dynamic stack

[Smilediver]

I came to the part when I need to implement user space stack, and I was thinking what is the best way to do that. The stack itself is easy, but I want it to be dynamic, so it's size could be extended on demand.

My processes have a memory map consisting of virtual memory area's like code/data, heap, memory mapped files (not yet implemented), and now stack. I can simply define an area for stack, and when application will try to write to any address belonging to it, page fault handler will allocate and map new memory page automatically. Now, it's a bit unclear on how extending of that area should happen. As I see, there are 2 ways to do that:

1) Define hudge area for stack, something like 128 MiB, and simply let the page fault handler do it's job. But the most negative side of this is that stack size is still somewhat limited, and it also eats quite a chunk from the process memory.

2) Reserve a small amount of space below the stack (something like one 4 KiB page), and when application writes to that, then extend the size of stack by including this reserved page, and make another reservation for later. This way stack can grow indefinitely. But I'm not sure about this one, since application could allocate 5 KiB for local variables by increasing esp, and if it wrote to the last bytes it would jump over the reserved page and app would crash. I could increase reserved size, but you never know what's on the programmers mind, and how much he will allocate on stack.

Any other ideas? Maybe you know how linux or windows do this? Thought, on windows I think the stack size is static. :-/ Any food for tought is welcome.

[Colonel Kernel]

Any other ideas? Maybe you know how linux or windows do this? Thought, on windows I think the stack size is static. :-/ Any food for tought is welcome.

Windows does exactly what you described in 2). For the case where more than 4K of local variables are allocated, I think it's up to compilers to generate code that touches stack pages sequentially when allocating such a "jumbo frame".

[Avarok]

Allocating stacks on demand is easy. You simply need to address it upside down (from the high pointer to the low pointer, expanding down)

The amount of address space you define for anything will not affect it's memory consumption unless you mark it present before it's used. You could, if you so desire, allocate the last half of 64-bit addressable space to the stack and have 4Gb of stack space for each program that they *might* use.

If you want more than one stack (I do), you can do so. The thing to remember is that you're polluting *addressable locations* not actual memory. Also, if you run a tight ship, processes are less likely to run away and eat the entire system's hardware resources without triggering any alarms.

I like running a tight ship. The page fault handler and the context switcher keep tabs on the size of the stack and make sure it doesn't go outside the program's capabilities values.

Enjoy.

[Smilediver]

The amount of address space you define for anything will not affect it's memory consumption unless you mark it present before it's used. You could, if you so desire, allocate the last half of 64-bit addressable space to the stack and have 4Gb of stack space for each program that they *might* use.

Yeah, but it eats the address space. If I define all 4 gigs for stack, then I can't define this area as anything else, because when it will hit a page fault, then I will not know if it was access to stack or heap or anything that is in the same address space.

Anyway, I have an idea, but I don't know how feasible it is. I could simply check the esp register in my page fault handler and see if it's bellow current stack area. If it is, I can extend stack's area. But I have a doubt... are there any programs that actually access the stack below the esp pointer? At least I haven't seen a situation like this, but you never know... I guess I'll have a meg or so as reserved for stack right bellow the stack area for situations like this.

[AJ]

Hi,

Another way to do this is in your process information structure have the following defined:

Code: Select all

struct myprocess
{
...
heap_start;
heap_end;
stack_base;
stack_top;
...
};

The heap values are, of course, extended by a call to sbrk(). As the stack always expands consecutively, all you have to know is that if the page below your stack has a PFE (and ESP is set to that value), you need extend stack_top downwards by one page.

Cheers,
Adam

[Avarok]

Exactly what I was thinking (about the stack).

You just keep something for Page Fault Exceptions (PFE's) that notices your stack needs more space. If it needs more, you check if the one below it is already marked present via the Present Flag. If it is, you need to re-address (mmap) your stack somewhere else and reflect that in ESP/EBP (the only two things that should point to the stack). Then the stack can theoretically grow without address concerns. Now you just gotta tell it when to stop.

[Smilediver]

Ok, guys, thanks for the input! The only thing holding me back is a problem with a tss descriptor. But when I'll fix that, I'll get working on the stack. Thanks again!

[JAAman]

If it is, you need to re-address (mmap) your stack somewhere else and reflect that in ESP/EBP (the only two things that should point to the stack).

no, ESP and EBP arnt the only things pointing to the stack -- each stack frame usually stores the previous EBP (to restore at procedure termination), and some calls may store esp (for example -- the exception which triggered the remapping will store the esp for the old stack on the kernel stack -- though that particular one will be easy to change) -- and local pointers to stack-allocated variables will also reference the stack (not sure how often this happens though) -- so in reality, to move the stack will require finding and changing possibly hundreds of pointers -- many of which you will not have any way of finding (of course if your using a combination of segmentation with paging, then you can eliminate this by altering SS to compensate -- but this makes memory management much more complicated, and most compilers usless)

[bewing]

JAAman is right. And pointers to small, locally defined character string variables, arrays, and structures get passed around (especially into functions and subroutines) A LOT. Once a stack has been started at a particular address, it is stuck there, permanently. It can only grow down to the next allocated space in the address space, and that's it. So this thread's original point is correct -- there *is* a problem here. But it is insoluble. If you have multiple stacks in an address space, you have to space them out a bit, and (once you've put the 2nd one in there) the spacing determines the maximum stack size before it overflows and begins to corrupt the userspace memory.

[Avarok]

Hmm... do local variables have to *point* to the stack? I mean, having a dynamically relocatable stack can hold a great deal of value. If you can get away with assuming nothing can point in on the stack but EBP and ESP, then you can.

You can still do mov EAX, [ESP+8] and then later put it back in the same spot. You can still use [EBP+4] as a local variable. You just can't do a mov EAX, ESP, PUSH EBX and expect EAX to be correct.

It might help to notice that you're only potentially re-addressing on a page fault , which will only happen during a push (and very rarely).

It *might* be worth it, depending on your design objectives. I mean, my OS isn't designed for compatibility with anything, but it's supposed to be secure and fast. This is in line with that.

[Crazed123]

Hmm... do local variables have to *point* to the stack?

Local variables do not point to the stack at all unless they are pointers set to do so.

But to interpret your babble and explain... Yes, local variables must be allocated on the stack. It is the most convenient data structure for such allocations, and it is the data structure used not only by the processor but by nearly every compiler on the planet targetting that processor.

[senaus]

I've been thinking about this recently, and came up with a method you might want to consider.

Instead of moving the stack if there is no space for it to expand, why not leave the original mapping in place, then allocate another region of virtual memory (double the size of the old stack region), mapping the old stack pages into it along with a fresh page for expansion, whilst leaving the old stack intact? That way, pointers into the 'old' stack are still valid, and by tweaking esp to the new value, pointers to freshly allocated variables will be valid as well. Existing pages are mapped into the new region, so if the user wants to address over the boundary (e.g. [esp + 8]), this is valid too.

Long sentences... phew!

Perhaps this will explain it better:
http://dyknl.sourceforge.net/img/dev/mm-ksp.png

[Avarok]

idea++; // awesome!

So basically we're double-mapping the original stack, with our new duplicate being in a emptier address space.

I like it very much.

Next problem is how do you (when do you) clean it?

The oldest stack is most likely the most long-living one (first in, last out). For eternally running programs, you can't just leave it dirty?

[bewing]

I think that yes, he means "never". You just leave it dirty.
The thing is, stacks are not supposed to grow downward forever. Eventually, they are supposed to "unwind".
So, the reality is that it's the NEWLY allocated stack area that should wind up getting discarded first.
If a program were to allocate a big area on the stack (call it A), and then call a subfunction that then allocates another big area on the stack (call it B) (in order to trigger this whole multi-stack allocation setup), the whole point of allocating A in the first place is that either it would be in constant use by the subfunction, or it would be needed when the subfunction terminates.
If the application allocated A, and then it was never used again after the subfunction was started -- that would be an example of horrible programming practice, and would deserve whatever performance penalty was involved in having the multiple stack setup sitting there forever.

And I'm beginning to agree, also. This is sounding like a good idea. It allows you to allocate and pack multiple stacks for multiple threads into a small area of "allocation space" -- and still let them all grow dynamically.

[senaus]

I'm glad you both like the idea, thanks for the feedback!

Next problem is how do you (when do you) clean it?

Do you mean "when is the newer stack freed once it is no longer being used?" I plan to have an array of stacks in the thread control block, tracking where the regions are and which one is the newest. The kernel would then probe blocked threads when it needs the memory, checking whether the thread's stack pointer has left the newer region. If it has (and it will eventually, as bewing says, the stack will unwind), the newer region will be freed.

Thanks,
Sean