You can usually allocate objects like this up to a few kilobytes or more without using "new"

In the past I've done "char x[500000000L];" in a function with no ill side-effects. I'm not saying it was a good idea, but there's nothing technically wrong with doing it.

I actually did it only to see how Linux would handle such a large stack allocation. Linux handled it with no problem, and since my code didn't touch any of the array's contents, I'm pretty sure Linux didn't allocate real memory for the whole array (which means I could have called the function recursively until the process's address space was exhausted, without consuming memory for other processes to use).

There is *NOTHING* automatic about the stack. You can *easily* stomp all over it and wreck yourself. In fact, that's exactly how buffer overflow exploits work.

It depends on the runtime environment. For example, in Linux (as I mentioned) it works fine. I just tested a program that writes to the array, either forward, backward, or randomly. The size of the stack is limited to the value of "ulimit -s", which was initially 8192 (8MB). I raised it to 2GB and then could make my array almost up to 2GB in size with no problem. I verified that the compiler wasn't doing anything funny behind my back like allocating the array in the bss segment. It was only doing a plain "subl $8000016, %esp" inside my function, as it should.

That's not how a buffer overflow works. A buffer overflow happens when a program writes data outside a buffer. What I'm doing is allocating a buffer and writing within its bounds. The worst that happens in my case is a segmentation violation if the OS refuses to allocate real memory for the stack (and thus the buffer that is on the stack). This is therefore a stack overflow. There is no smashing of return addresses or anything like that which happens in a buffer overflow.

*snip*

Where do I begin?

[*]Every process gets its own private virtual address space (2^32 bytes on 32-bit systems, ignoring PAE etc).

[*]Linux allocates real memory for a process only when the process accesses the memory (this happens per-page, but that detail's not really important at this conceptual level).

[*]A process can access any memory in its address space as long as it falls within the limits defined by its data segment size and rlimits (gettable/settable via the ulimit shell command, or the getrlimit()/setrlimit() syscalls).

[*]If a process reads from or writes to memory outside of its limits, or writes to read-only memory (eg, text segment), Linux cleanly segfaults that process.

What this all boils down to is that Linux essentially gives every process a ridiculously huge stack (almost the full address space, in fact)

With virtual memory, a huge stack is neither wasteful nor slow (there is a slight performance penalty as the kernel has to handle page faults, but that's the price of virtual memory). With a stack size limit in place, if a process "run[s] off the end of the stack", Linux will segfault it. It won't ever let it "wreak havoc in random memory".

The Linux kernel is a lot more intelligent than you give it credit for.

Not so much.

Completely false. Linux has a fixed stack size of 8mb by default. Stacks are *always* a fixed size.

A huge stack has overhead because it has to be swapped out every time a context switch happens (which, fyi, happens thousands of times a second).

What you seem to be forgetting is that stacks are per *THREAD*, not per process. They have management costs that the heap does not.

You are also banking on *where* the stack is in relation to everything else if you run off the end. If you happen to own the random memory off the end of the stack, you absolutely will wreak havoc in it.

You are also forgetting things like the CPU cache and paging. The bigger your stack gets, the more likely it will be swapped to disk. Allocate 1GB on the stack, and suddenly returning from that function takes tens of milliseconds as it has to fetch the stack from disk. And if you can't keep the relevant section of the stack in the CPU cache, say goodbye to any hope of decent performance. Now your function calls are slower, locals are slower, even just returning is slower.

Otherwise you are fighting against the system just to entertain your own insanity.

Nope, this is false. The stack is not a fixed size in Linux. The stack starts at perhaps one or two pages upon process execution (via execve()), and it expands up to a limit, either the address space limit or a resource limit. Where did you pull the 8MB figure from, anyway?

All memory that belongs to a process and is swapped in must be swapped out (that is, the MMU's page tables modified to point to the incoming process's memory pages) at each context switch. And I believe the scheduling quantum is on the order of 100 times per second, not 1000's of times per second (though it's possible to have more frequent context switches in some scenarios).

In Linux, each thread is a process that just happens to share its address space and other resources with some other processes.

Of course it will wreak havoc on its own memory. The stack is placed at the top of the process's address space. It grows downward while the heap grows upward. If the process needs enough memory on the stack for this to be a problem, it would need just as much on the heap instead, where it would also be a problem for the process.

I did not forget about those. You are forgetting about LRU, or whatever specific page-replacement algorithm that Linux uses. Sure, some pages of the stack may be swapped out, but only the pages that haven't been used recently. The pages that are actively being used are the very least likely to be swapped out (they may be swapped out if the system is thrashing, but that's the same whether this process uses the stack heavily or not).

Regarding the CPU cache, it's the same issue too. Assuming the access patterns of a memory block are similar whether it's stored on the stack or on the heap, the CPU cache should behave practically identically. The CPU cache doesn't (afaik) make any distinction between the stack and the heap. It's all just memory pages to it. (I'm referring to the data cache here; the instruction cache isn't affected, since instructions are fetched from the same pages either way.)

RLIMIT_AS
The maximum size of the process's virtual memory (address space)
in bytes. This limit affects calls to brk(2), mmap(2) and
mremap(2), which fail with the error ENOMEM upon exceeding this
limit. Also automatic stack expansion will fail (and generate a
SIGSEGV that kills the process if no alternate stack has been
made available via sigaltstack(2)). Since the value is a long,
on machines with a 32-bit long either this limit is at most 2
GiB, or this resource is unlimited.
...
RLIMIT_STACK
The maximum size of the process stack, in bytes. Upon reaching
this limit, a SIGSEGV signal is generated. To handle this sig‐
nal, a process must employ an alternate signal stack (sigalt‐
stack(2)).

You can pretty easily figure out the default stack size using pthreads: https://computing.llnl.gov/tutorials/pthreads/#Stack

I suspect the kernel uses the same mechanism to expand the stack that it uses to detect when a process touches a page that is not swapped in—with page faults. When a process touches a page below the stack that hasn't been mapped to the process, the kernel expands the stack, allocates real memory for those page(s), and maps those new pages to the process. A similar thing happens with the heap (where the upper limit is defined by brk()).

The setrlimit(2) man page even mentions automatic stack expansion and how some of the limits can limit this expansion:

A similar thing happens with the heap (where the upper limit is defined by brk()).

With setrlimit(RLIMIT_STACK, ...), a process can make its maximum stack size smaller or larger.

Pthreads on Linux probably set the maximum stack size of threads using setrlimit(RLIMIT_STACK, ...).

You may have a valid point here. However, if a program is large and/or complex enough to warrant using multiple threads, then memory allocation will have more subtle issues than deciding whether to store a large block of memory on the stack or on the heap. Most programs in Unix/Linux are single-threaded, though, so this doesn't become a factor for most programs.

You may have a point here too. Then again, gcc has the option -fstack-check which will cause a SIGSEGV upon stack overflow (which you can catch in a signal handler by using sigaltstack()).

That may be so (and I was aware that CPU caches are small), but some allocation sizes and memory access patterns may be faster by putting it on the heap, and some other configurations may be faster by putting it on the stack. If the process is accessing at least one byte in each page of a >=256K block of memory, it doesn't matter much whether it's on the stack or on the heap. The current stack page (the one that the stack pointer points to) is probably going to be flushed from the cache either way.

After all is said and done, I would personally put up to a few kilobytes on the stack in each stack frame, but I don't worry if I occasionally put more than that.

setrlimit is a POSIX thing, not necessarily a Linux thing. Linux isn't actually 100% POSIX compatible.

I like how you reject pthreads saying it was designed to support various implementations, then turn around and reference a POSIX man page. You realize pthreads is POSIX threads, right? Same standard.

RLIMIT_STACK
This is the maximum size of the initial thread's stack, in bytes. The implementation does not automatically grow the stack beyond this limit. If this limit is exceeded, SIGSEGV shall be generated for the thread. If the thread is blocking SIGSEGV, or the process is ignoring or catching SIGSEGV and has not made arrangements to use an alternate stack, the disposition of SIGSEGV shall be set to SIG_DFL before it is generated.

Most programs in Unix/Linux are single-threaded? Bwahahahaha, no, no they aren't. Most programs are multi-threaded. The vast majority are multithreaded. Sure, those command line utils aren't, but there aren't that many of them.

Threading is *insanely* critical in modern systems, even for programs that don't appear threaded (as in, they don't use much CPU).

You *cannot* ignore threading, it is hugely important and continues to become more and more important as time goes on.

In the case of this thread, it absolutely seems like a case of "a little knowledge is a dangerous thing". Particularly you seem convinced that the stack is faster than the heap - which stops being true as soon as you start using the stack as a heap. Go do some actual testing, get some real numbers.

Besides, if Linux were to allocate 8MB for the stack in every process, that would be extremely wasteful and slow. I currently have 320 processes (or 575 if you count threads individually). If each thread had a fixed 8MB stack, that would be 4.5GB set aside just for stacks! Do you really think there is actually that much stack space reserved on my system? I didn't think so. What happens in Linux is what I've said happens. The stack grows as a process needs it, up to the limits defined by setrlimit.

Um, yes. I had it right.

Of the 3843 programs that I have under /usr/bin, only 1385 (36%) are multi-threaded, so the majority are single-threaded.

I agree that threading is important, but it's frankly not as important in the Unix world as you make it out to be. Forking is cheap in modern Unix, making it practical to use full processes in place of threads in many cases (there's little distinction between threads and processes, after all). Contrast that with Windows, where process creation is relatively expensive, so you see threads used much more heavily there*. That's one reason that Cygwin has poor performance for some tasks (eg, running a program inside a loop in the shell).

That's true. But allocating even 16KB on the stack is not going to give you any problems (I do admit that allocating many megabytes on the stack at a time is silly for practical purposes). With the default 8MB maximum stack size, you'd have to nest your function calls about 500 times before you overflow the stack. If you're writing a recursive function, it'd be stupid to allocate that much space on the stack. With any other non-recursive function, it's no problem!

* Incidentally, I'm currently writing a multi-threaded Windows service in C++ at work. It's several hundred lines long so far (it's more or less a prototype at this stage), but had I been writing it for Linux it would've been a much shorter script to do the same thing. I'd probably fork the script (using & in Bash, for example) to run a few different parts simultaneously (as "threads"), and also call external programs to do some of the work for me. Overall performance would be lower than in C++, but development time would also be much lower. Performance wouldn't really be that much of an issue anyway, since this (hypothetical) script could easily keep up with what it needs to do.

Absolutely. That's exactly what happens. It isn't using real memory, of course, but each one of those has an 8MB stack (except for the ones that changed it, of course).

And how did you arrive at those numbers?

Then again, why on earth are you writing C++ on Windows for something that isn't performance critical? Seriously, Win32 is one of the worst APIs known to man - why would you subject yourself to that torture when the bliss of C# is so close? Hell, if you can get away with a scripting language use Python. Or if by "service" you mean a web service, check out NodeJS - which I believe now has a Windows port.

I think you and I agree on the mechanisms and end results but disagree on the exact meaning of "stack size". I say it means the peak usage of stack space (which obviously can expand during a process's lifetime), whereas you (I think) say it means the most stack space that the process can use. Am I right about that?

It has the benefit of allowing the programmer not to worry too much about where objects are being allocated. How often do you figure out how large each of your C++ classes (or third-party C++ classes) are before deciding whether to allocate them directly on the stack or to allocate them with "new"? Granted, a large class probably points to a flawed class implementation more than anything else, but I think my point still stands.

I do mean a Windows service, not a web service. This service will be running on our client's Windows XP terminals which don't have .NET or any scripting facilities (besides, ugh, VBScript), and our service needs to be fully self-contained if possible for one reason or another. I even suggested using a scripting language like Python to the project manager, but he shot down that idea. For this project I just have to live with the awful Win32 API (it is terrible!).

Or you could just allocate most everything on the heap and use auto_ptr, sidestepping the need to figure out how large a C++ class is entirely AND preventing stack abuse AND not need to worry about calling free.

It always amazes me how little people actually know about the C++ STL