I'm looking for the most elegant (in terms of assembly, so optimization hacks etc) way to allocate large stuff on the stack (larger than a page, not too large though, let's say 64k bytes for example) on Windows. (Wine too but w/e)

As you know, Windows keeps a guard page at the bottom of the currently committed stack, and accessing it leads to it allocating more stack (i.e. "growing" the stack) up to a limit. This is usually done in function prologues via the _chkstk function in HLL compiled code, which basically does something like (not exactly but you get the point): i.e. it "touches" the stack at every page so that it doesn't miss the guard page. If it touches the guard page, the OS silently eats the page fault and allocates more stack space, otherwise the probe does nothing.

I'm looking for a way that does not require probing the stack. I'd like to do it with no function calls either (an implementation with a "chkstk" function would be simple and I'm already aware of), but instead with exception handling. The currently committed "bottom" of the stack is found at [fs:8] for 32-bit.

So I was thinking to have something like:

• sub from esp required amount (e.g. sub esp, 65536)
  
• compare it with [fs:8] and see if it's below (carry flag is set)
  
• if it is below, somehow trigger an exception (probably have to move esp back too?), the exception handler will allocate the stack until esp's location (I'll "return" from it in a custom function that probes the stack since I don't want to cause page faults from within an exception handler, it would kill the app)

This has no function calls, but how do you conditionally trigger an exception based on carry flag? Is there an elegant trick that does not hurt the performance of the common case which is when allocation is not needed? (i.e. I need to fall-through the jump in the general case). I can use a conditional jump, but then how do I know where to "return" after the exception? (I'll have only one exception handler to deal with it, not one per function, but one per all such functions!).

The "obvious" one like: the problem with this is that it is not a fall-through in the general case, which hurts performance. Yeah, I can do a jb followed by a jmp but that's a bit more ugly, I'm asking basically, is there some tricky instruction that can cause a fault only when carry flag is set?

Caveats:

• my application is a DLL -- a plugin, not a library, technically. It gets called back from processing functions (e.g. like VST in Wavosaur, though that's just an example), so I do *not* control the stack whatsoever on entry.
  
• it is multi-threaded, and I want an elegant solution, threads are also created by the host of the plugin, but also from within the plugin, so no I cannot just take the stack size from the module, as each thread could have different stack size

Because of the above there is another problem: how do you get the MAXIMUM STACK SIZE of a given THREAD in Windows? I need to do this from the exception handler to see if it's even safe to probe the stack or not.

Hmm I guess this is longer than I expected. I don't expect a solution but maybe I'm missing something I'm just asking out of curiosity and because it would be nicer than just calling a function to do it. (which has more overhead for the common case)


EDIT: Oh and I'd like to incorporate this into my GCC plugin to tweak the prologue too, so I want it as good as possible even if my app by itself doesn't have any measurable improvement.

Also, I've actually measured the following cases from the above stack probing question: Processor Intel Xeon E3-1241 v3 (Haswell) (note that no combination of test, even with constant zero, provided any differences)

Statically allocate. For the stack size: It is defined when the thread starts, so for the above it is 1MB for the main thread, and when you create a new thread you state the stack size in your call to the API.

Well that's a solution in other cases but 1) not what I want and 2) not useable in this situation

The host (executable) creates threads and then processes them in parallel, which can also happen to be callbacks to my function (if they're used as plugins in that chain). So I don't control the threads' stack space at all.

Yes I can create threads from within my own plugin too, but I'm talking about the threads created by the host which end up calling my plugin's callback.

What problem are you trying to solve? Do you have some performance issue? Or something else?

I doubt this would be a performance issue unless the buffer size is set to like 1 sample or something (so then most of the overhead is in calling the function etc).

However, I just want to know if I'm overlooking something. Specifically:

1) is there an instruction that can cause a fault only when carry flag is set? (or something like that, see my cmp above, or an alternative method?)
2) how do you get the maximum stack size of the thread in Windows? (maximum reserved, not allocated, the latter is easy, found at [fs:8] -- I don't know the thread's origins, however)

For my use case it's probably not significant, but when I'll incorporate into my GCC plugin's prologue tweaker, I'd obviously prefer to have the "better" method. It's just in my nature: if you do something, do it right if you can.

There is INTO, not the carry flag there, but you could also use the overflow flag I suppose.

But I'm still not sure what problem you are trying to solve. If not for performance then what?

I mean, it is for performance, but not necessarily "significant" performance (depending on the DSP buffer size). I didn't mean it's slower, though.

INTO looks interesting, thanks, it doesn't generate an interrupt when OF is not set right? (btw a trick I meant like.. for example using cmovc, but I know that it will always trigger the fault though)

But for my second question I found this SO answer. But I'm not sure I understand, why can't he just give some stupid code example, ffs. I'll look into VirtualQuery to see, never used it before.

If I'm not mistaken, his "first" VirtualQuery call sounds rather pointless: such information (base address of committed stack) is already at [fs:8] Or I don't get it.

I don't know of anything that can do what you want. Windows isn't really designed with that in mind. Usually large buffers are expected to be allocated by other means that don't use the stack. And naturally the meaning of "large" is not given so you just have to guess where the trade-off point is.

I'd expect that base addresses for stacks are from the top going down, not the lowest address.

"cmovc eax,[0]" will always generate a fault regardless of the flag value. I discovered this a long time ago and it is annoying. I wanted to conditionally read a memory address if is wasn't zero:

Yeah, I'm aware about cmov, it was just an example (i.e. that I'm not necessarily looking for an instruction made just for this purpose, like INTO is, but can be any such trick).

It looks like the second problem is solved due to VirtualQuery -- I only need to call it once to get the reserved base address if it's according to the documentation (I'll test it in a few minutes and report back). The stack layout is like this:

Now to figure out a hack for first one (or how to get carry into overflow flag, and test if INTO works on Windows in the first place, maybe it generates faults all the time due to privilege stuff)

IIRC:

Stack memory base address != data memory base address.

Stack points to the top, data points to the bottom.

I'm afraid I don't understand what you mean? Can you explain it simpler?

I tried VirtualQuery but the results aren't what I want. I tried both BaseAddress and AllocationBase from its output struct -- both are bad.

BaseAddress seems to be the [fs:8] so it's pointless. AllocationBase doesn't make much sense -- it's always 262144 (1 shl 18 ) bytes below the top of the stack even if I change the stack's size with 'stack' directive.

Just to make sure I even tested it in FASM, here this code: gives 262144 in eax, no matter the value in the 'stack' directive, WTF? (note that [fs:4] - [fs:8] gives 8192 bytes only, so it's not that)

Stack base address is the top of the memory range, and it expands downwards. Data and code base addresses are the bottom of the memory range and expand upwards.

Yeah but I don't touch the data/code base addresses at all here. I view the stack as one large "VirtualAlloc" block in this context (going up, hence the "Base address" of the stack is its final limit since it comes down from the "end" of the block).

BTW, it actually works. Apparently 262144 is the lower limit, and seems to be the default of FASM for some reason. I thought it was 1MB, that's why i got confused. If I use larger values, it reports properly, so this problem is solved.

So the piece of code above works to determine the absolute bottom of the stack (well, the absolute bottom is at blah+4 in it, that code is just subtracting the top from it to get its size -- blah+4 of course refers to AllocationBase, don't worry I won't hardcode offsets when coding it for real this was just a quickie I also don't like using invoke in real asm code...).

What the code does is: it gets the "address of the last committed page" of the stack, uses it in VirtualQuery to get the "address of the base of the entire stack".

For the other problem, I'm thinking a "design" of the prologue like this: In this respect, there is minimal overhead for when the stack doesn't need probing -- only one (hopefully predicted) branch and a comparison. I don't see how it could be made with less overhead (in this respect I'll need a vectored handler I guess).

The Exception Handler will recognize this pattern, and scan through the prologue to find out how much to subtract esp by, and then probe the stack, and finally return execution after the jb instruction with the proper stack. Of course I'll first check to see if it fits within the limit of the stack (found by VirtualQuery), if it doesn't well, stack can rest in peace (I'll just show a stack overflow message or something out of the handler). But before I implement it, I'd like to know your ideas, is it good or am I missing something obvious? If you got any elegant tips or something

(again: requirement is to be as MINIMALLY invasive on "normal execution not requiring probing" as possible -- if it's slow when it probes the stack is not a problem since it happens ONCE, but this DSP function gets called many times per second on multiple threads, depending on buffer size, with 1 sample it's like 44100 times per sec and I want to keep its CPU usage low since it's realtime and one out of many effects)

I know you love testing/profiling, but unfortunately I cannot test it here. I mean, I did test it in a loop, but there's literally no difference, you know why? The misprediction happens only for the first time or first few times, so in a testing loop with 1<<31 iterations, it won't make a dent.

However in real code, this won't be ran in a loop, but of course on every call to the function. It may not be a big deal, but if it's a "free change" then why not? I don't see a way to find out if a branch was predicted correctly or not... maybe with rdtscp since it blocks speculative execution?

(and I don't have the actual function's code yet to test, just open to speculation so far)

BTW, I realize I can allocate much more of the stack if I have the information from VirtualQuery and not bother with the "cmp/jb" at all and have all the stack allocated always. But that allocates stack space for each thread, seems a bit wasteful, especially if the host increases reserved stack size "just for the heck of it". Two instructions shouldn't really matter, assuming the branch gets predicted to fall-through (not taken). I hope.

NOTE: This alternative is also dangerous if I use too high a stack, as the stack pointer could go below the stack entirely, and into something else (Heap?) and not crash at all but corrupt random data (because it points to valid pages). That's bad. So I'll still go with the cmp/jb and hlt idea I guess, much safer, since I don't control the incoming stack or its size. I'd like it to be as "bulletproof" as possible in any stupid host that can use my plugin.

I suppose an alternative could be to simply use the stack without testing anything, and in your exception handler do the probing. Make sure to use the full SEH structure to set the safe stack values.

You could also replace your HLT with a call to the probing function and a jmp to reenter the function where it left off.

I tried it the first time but it doesn't work for two reasons:

1) Windows *wants* the stack (at esp) to be available when exception occurs; SEH uses *this* stack to call your code, not a different one, which sucks. What happens is Windows will just kill the process (Wine seems to work fine but Wine apparently allocates all stack on default thread?)

2) It's dangerous if I use something larger than 65536 -- imagine I subtract esp below the entire stack, into valid memory (Heap?), then there won't be any exception, only silent corruption of random data (this was a huge thing in earlier Linux versions, not sure if Windows suffers from it, but yeah, it sounds bad).


To solve (1) I could instead probe just the end of the stack I want before subtracting, i.e.: this will fault properly, but then again, it's only 1 instruction less now and a bit less safe due to (2) (assuming jump gets predicted)


The call sounds good, not sure why I hadn't thought of it, perhaps I still had in my mind to "not touch the stack"... thanks

Hmm, I see: Annoying.