8

(I think there's a high chance of this question either being a duplicate or otherwise answered here already, but searching for the answer is hard thanks to interference from "stack allocation" and related terms.)

I have a toy compiler I've been working on for a scripting language. In order to be able to pause the execution of a script while it's in progress and return to the host program, it has its own stack: a simple block of memory with a "stack pointer" variable that gets incremented using the normal C code operations for that sort of thing and so on and so forth. Not interesting so far.

At the moment I compile to C. But I'm interested in investigating compiling to machine code as well - while keeping the secondary stack and the ability to return to the host program at predefined control points.

So... I figure it's not likely to be a problem to use the conventional stack registers within my own code, I assume what happens to registers there is my own business as long as everything is restored when it's done (do correct me if I'm wrong on this point). But... if I want the script code to call out to some other library code, is it safe to leave the program using this "virtual stack", or is it essential that it be given back the original stack for this purpose?

Answers like this one and this one indicate that the stack isn't a conventional block of memory, but that it relies on special, system specific behaviour to do with page faults and whatnot.

So:

  • is it safe to move the stack pointers into some other area of memory? Stack memory isn't "special"? I figure threading libraries must do something like this, as they create more stacks...
  • assuming any area of memory is safe to manipulate using the stack registers and instructions, I can think of no reason why it would be a problem to call any functions with a known call depth (i.e. no recursion, no function pointers) as long as that amount is available on the virtual stack. Right?
  • stack overflow is obviously a problem in normal code anyway, but would there be any extra-disastrous consequences to an overflow in such a system?

This is obviously not actually necessary, since simply returning the pointers to the real stack would be perfectly serviceable, or for that matter not abusing them in the first place and just putting up with fewer registers, and I probably shouldn't try to do it at all (not least due to being obviously out of my depth). But I'm still curious either way. Want to know how these sorts of things work.

EDIT: Sorry of course, should have said. I'm working on x86 (32-bit for my own machine), Windows and Ubuntu. Nothing exotic.

Community
  • 1
  • 1
Alex Celeste
  • 12,824
  • 10
  • 46
  • 89
  • 1
    The answers to these questions will be highly platform-specific. Please mention what platform you're working on. – Oliver Charlesworth Mar 03 '13 at 23:08
  • Can you be more specific what you want to do? Maybe provide an example of what do you mean by your virtual stack pointer and how you intend to return control to a host process? – Roasted Yam Mar 03 '13 at 23:15
  • The virtual stack pointer is just a regular C variable that points somewhere into the memory block. "Returning to the host program" literally just means returning from the script function (so if we messed about with registers, it would mean setting them back as they were found before returning). Essentially the same things as you would have in an interpreter; the interpreter object maintains its own separate program state. – Alex Celeste Mar 03 '13 at 23:20
  • 1
    Have you considered simply running the interpreter (or whatever it is) in a separate thread? That way it will automatically get a nice, OS-managed stack, and will avoid any of your above concerns! – Oliver Charlesworth Mar 03 '13 at 23:24

3 Answers3

4

All of these answer are based on "common processor architectures", and since it involves generating assembler code, it has to be "target specific" - if you decide to do this on processor X, which has some weird handling of stack, below is obviously not worth the screensurface it's written on [substitute for paper]. For x86 in general, the below holds unless otherwise stated. 

is it safe to move the stack pointers into some other area of memory?

Stack memory isn't "special"? I figure threading libraries must do something like this, as they create more stacks...

The memory as such is not special. This does however assume that it's not on an x86 architecture where the stack segment is used to limit the stack usage. Whilst that is possible, it's rather rare to see in an implementation. I know that some years ago Nokia had a special operating system using segments in 32-bit mode. As far as I can think of right now, that's the only one I've got any contact with that uses the stack segment for as x86-segmentation mode describes.

Assuming any area of memory is safe to manipulate using the stack registers and instructions, I can think of no reason why it would be a problem to call any functions with a known call depth (i.e. no recursion, no function pointers) as long as that amount is available on the virtual stack. Right?

Correct. Just as long as you don't expect to be able to get back to some other function without switching back to the original stack. Limited level of recursion would also be acceptable, as long as the stack is deep enough [there are certain types of problems that are definitely hard to solve without recursion - binary tree search for example].

stack overflow is obviously a problem in normal code anyway, but would there be any extra-disastrous consequences to an overflow in such a system?

Indeed, it would be a tough bug to crack if you are a little unlucky.

I would suggest that you use a call to VirtualProtect() (Windows) or mprotect() (Linux etc) to mark the "end of the stack" as unreadable and unwriteable so that if your code accidentally walks off the stack, it crashes properly rather than some other more subtle undefined behaviour [because it's not guaranteed that the memory just below (lower address) is unavailable, so you could overwrite some other useful things if it does go off the stack, and that would cause some very hard to debug bugs].

Adding a bit of code that occassionally checks the stack depth (you know where your stack starts and ends, so it shouldn't be hard to check if a particular stack value is "outside the range" [if you give yourself some "extra buffer space" between the top of the stack and the "we're dead" zone that you protected - a "crumble zone" as they would call it if it was a car in a crash]. You can also fill the entire stack with a recognisable pattern, and check how much of that is "untouched".

Mats Petersson
  • 126,704
  • 14
  • 140
  • 227
  • Any recursive algorithm can be transformed (usually fairly painlessly) into a very similar iterative one that uses a heap-allocated stack structure ("stack" in the data-structure sense). – Oliver Charlesworth Mar 03 '13 at 23:27
  • Yes, agreed. But whilst it's relatively easy from a technical perspective, it does add a layer of complexity to some code that started out real simple. A (well balanced) binary tree can search through 1M entries in 20 recursion levels - assuming the stored data for each recursion level isn't too large, that's certainly within the bounds of even a fairly small stack. – Mats Petersson Mar 03 '13 at 23:34
  • Answer seems good'n'clear, thank you! As far as recursion goes, I was planning on making the second stack reasonably large, so wasn't particularly worrying about small bounded recursive situations. – Alex Celeste Mar 03 '13 at 23:52
  • Well, unbounded [or "large bounded"] recursion is obviously rarely a good solution to any problem. If your recursion levels aren't "reasonably predictable and less than a few dozen", then recursion is probably the wrong solution for the problem. And yes, making the stack reasonably large saves a lot of other hassle as well. – Mats Petersson Mar 03 '13 at 23:58
2

Typically, on x86, you can use the existing stack without any problems so long as:

  • you don't overflow it
  • you don't increment the stack pointer register (with pop or add esp, positive_value / sub esp, negative_value) beyond what your code starts with (if you do, interrupts or asynchronous callbacks (signals) or any other activity using the stack will trash its contents)
  • you don't cause any CPU exception (if you do, the exception handling code might not be able to unwind the stack to the nearest point where the exception can be handled)

The same applies to using a different block of memory for a temporary stack and pointing esp to its end.

The problem with exception handling and stack unwinding has to do with the fact that your compiled C and C++ code contains some exception-handling-related data structures like the ranges of eip with the links to their respective exception handlers (this tells where the closest exception handler is for every piece of code) and there's also some information related to identification of the calling function (i.e. where the return address is on the stack, etc), so you can bubble up exceptions. If you just plug in raw machine code into this "framework", you won't properly extend these exception-handling data structures to cover it, and if things go wrong, they'll likely go very wrong (the entire process may crash or become damaged, despite you having exception handlers around the generated code).

So, yeah, if you're careful, you can play with stacks.

Alexey Frunze
  • 61,140
  • 12
  • 83
  • 180
2

You can use any region you like for the processor's stack (modulo the memory protections).

Essentially, you simply load the ESP register ("MOV ESP, ...") with a pointer to the new area, however you managed to allocate it.

You have to have enough for your program, and whatever it might call (e.g., a Windows OS API), and whatever funny behaviours the OS has. You might be able to figure out how much space your code needs; a good compiler can easily do that. Figuring how much is needed by Windows is harder; you can always allocate "way too much" which is what Windows programs tend to do.

If you decide to manage this space tightly, you'll probably have to switch stacks to call Windows functions. That won't be enough; you'll likely get burned by various Windows surprises. I describe one of them here Windows: avoid pushing full x86 context on stack. I have mediocre solutions, but not good solutions for this.

Community
  • 1
  • 1
Ira Baxter
  • 93,541
  • 22
  • 172
  • 341