11

I took a look at the draft C++0x standard, and as far as I can tell there is nothing about stack overflow in there. Searching for "stack overflow" yields no results, and searching for "stack" I've only gotten references to stack unwinding and std::stack. Does that mean that there cannot be a conforming implementation of the C++ standard, since there is no mechanism allowed for handling the error when memory is exhausted by a local object such as a huge local array?

The answers to this question indicate that at least the C standard does not mention stack overflow.

To make the question concrete, consider this program

// Program A
int identity(int a) {
  if (a == 0)
    return 0;
  char hugeArray[1024 * 1024 * 1024]; // 1 GB
  return identity(a - 1) + 1;
}
int main() {
  return f(1024 * 1024 * 1024);
}

and this program

// program B
int main() {
  return 1024 * 1024 * 1024;
}

I think the C++ standard does not allow any C++ implementation to do something observably different on these two programs. In reality program A won't run on any modern machine as it is allocating an exabyte of memory on the stack (imagine the function actually used the huge array so the compiler can't silently remove it to no ill effect). Does the C++ standard allow program A to fail?

Edit: The question is not whether the standard should define what happens on stack overflow, the question is what it says, if anything.

Community
  • 1
  • 1
Bjarke H. Roune
  • 3,667
  • 2
  • 22
  • 26
  • 2
    The standard does not have a notion of a physical computer with finite memory. In principle, no compiler can ever be standard-conforming, because you could always write a _very_ large program which cannot fit into any existing hardware and cannot be compiled, although it consists of valid, standard code but the compiler could not compile it. – Kerrek SB Jul 05 '11 at 23:22
  • 3
    @Kerrek Good point. However, the standard does have a notion of memory being a finite resource in terms of new throwing std::bad_alloc. If I had allocated the huge array using new, the standard _would_ allow program A to fail. What I'm wondering is if there is a similar notion that allows program A to fail as it is. – Bjarke H. Roune Jul 05 '11 at 23:28
  • You can certainly expect `new char[HUGE]` to fail, sure. But what if your source code contained billions of billions of functions? All completely valid standard C++... – Kerrek SB Jul 05 '11 at 23:29
  • Heap is, at some level, explicitly allocated; stack is automatically allocated, with the only control available often being a stack probe to force the stack to be extended. This means you can't check beforehand *and* there's usually no way to handle *or even recognize* the case where the stack runs into the heap. (Think about it: is it an oversize stack allocation or is it a wild heap pointer? A programmer can figure it out by inspecting the code (hopefully), but neither the kernel nor the system library can.) – geekosaur Jul 05 '11 at 23:34
  • 2
    The stack is an implementation detail that neither the C nor the C++ standards will touch with a ten foot pole. That's not entirely uncommon, VM languages obfuscate it too. This universally fits the 'oh crap, let's not do that again' category. If you run out of stack then you're an order of magnitude beyond what's reasonable. – Hans Passant Jul 05 '11 at 23:35
  • @Hans: "If you run out of stack then you're an order of magnitude beyond what's reasonable" - that's implementation-dependent, some implementations (especially if they don't have virtual memory) don't by default give a process/thread an order of magnitude more stack than is reasonable. On a PC, modern operating system, blah blah, of course it does. – Steve Jessop Jul 05 '11 at 23:47
  • @Steven: Have you tried writing for the old PalmOS 5.4? I think it had 12kB stack or something like that... – Kerrek SB Jul 05 '11 at 23:56
  • @geekosaur Are you sure that stack overflow can happen without being detected on modern systems? I'm certain that it *could* be detected if the compiler and OS cooperates, but I can also see that that might be associated with some overhead so it might not be done. If so, that scares me. – Bjarke H. Roune Jul 05 '11 at 23:56
  • @Kerreck: Symbian 8, same basic deal. I think the default stack size was 4kb, although of course there was a lot more RAM than that available, so you could up it if you realised that you need to. – Steve Jessop Jul 05 '11 at 23:58
  • @Bjarke: work it through. You are the OS's page fault handler, and a process has just triggered a page fault. How do you determine that it resulted from an oversized stack allocation? How do you determine that it was an uninitialized heap pointer? How reliable is this determination when the stack and heap are near each other? Ultimately the only way to be *certain* is to understand the intent of the code that triggered it — which is well beyond the abilities of any OS or compiler. – geekosaur Jul 06 '11 at 00:02
  • @Bjarke: I think that one of the qualifying characteristics to be a "modern operating system", at least in the world of full-fat devices, is to detect stack overflow. Usual procedure is to stick a guard page at the end of the stack, and indeed to page in more stack as required rather than pre-allocating much. Then the only real performance-related quibble is, if you're laying down a frame that's bigger than the guard page, do you do test accesses at size-of-page intervals to ensure you haven't jumped the guard page. – Steve Jessop Jul 06 '11 at 00:02
  • As geekosaur says, in principle you could hit that guard page for some reason other than stack overflow, but any other reason is UB, so it doesn't "matter" if the OS treats it the same way it would treat SO - page in more stack if possible/permitted, else kill the process or do whatever else the manual says is the result of SO. So there can be false positives, but it's not too much effort to ensure no false negatives. – Steve Jessop Jul 06 '11 at 00:03
  • @Steve: that last is precisely the screw case; you can have guard pages on both sides if you want (until they run into each other) but the farther away you get from the actual end of the allocation, the more uncertain the origin of a page fault becomes. – geekosaur Jul 06 '11 at 00:04
  • @geekosaur: but you can still avoid false negatives, hence you can always detect SO. You might falsely claim that some things are SO when actually they aren't, but that's false positives, it's not failing to detect SO when it does happen. In fact, another common characteristic of modern OSes is that the stack never gets anywhere near the heap - wonders of large virtual address spaces. Of course a program can imitate SO just by running wildly off the end of any automatically-allocated object, no need for the heap to be involved. – Steve Jessop Jul 06 '11 at 00:07
  • @Steve: take a close relative to that 1-exabyte example, a 2GB or 3GB stack allocation. It'll land in the middle of the heap on most modern systems. Is the compiler then required to do a page-by-page probe to allocate the stack, and if so how long are you willing to wait for a local stack variable to be allocated while the stack frame setup or `alloca()` call loops probing many pages? And even if you're willing to pay that price (since pedantically this means you "can" even if it's impossibly expensive), you *still* don't have absolute certainty about the page immediately above the heap. – geekosaur Jul 06 '11 at 00:14
  • @geekosaur: you don't really seem to be engaging with the fact that by resolving the uncertainty in favour of assuming that it *is* SO, you can absolutely avoid false negatives. As you say, the performance of probing 2GB in 4k increments might be a pain, but that's only the worst-case scenario for a compiler that knows the OS will place a guard page, but can't directly access info about the thread's stack to compute whether and how much the frame exceeds the currently-committed stack. In practice, compilers may well impose a <2GB frame limit anyway. – Steve Jessop Jul 06 '11 at 00:26
  • Assuming it is is assuming it is, not detecting it. I suppose you can just call it semantics and call it a day, since it's irrelevant anyway. – geekosaur Jul 06 '11 at 00:28
  • @geekosaur: detecting it means, "if it happens, saying that it happens". False positives are situations when you say it happens but it didn't happen. It is common to speak of detection with a possibility of false positives, since only false negatives are failure-to-detect, false positives are not. I'd call it, "the plain meaning of the terms" rather than "semantics", but of course plain, obvious meaning is one example of semantics ;-) – Steve Jessop Jul 06 '11 at 00:31

4 Answers4

14

I'm not sure if this is what you're looking for, but in Appendix B of the C++03 ISO standard there's the following notice:

  1. Because computers are finite, C++ implementations are inevitably limited in the size of the programs they can successfully process. Every implementation shall document those limitations where known. This documentation may cite fixed limits where they exist, say how to compute variable limits as a function of available resources, or say that fixed limits do not exist or are unknown.
  2. The limits may constrain quantities that include those described below or others.

(My emphasis) I take this to mean it is perfectly legal for the compiler to allow one of those functions to work while failing another, provided that the compiler states what limitations are in place and how they are computed from the resources the system has available.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • **If** that is all the standard has to say on the matter, then yes, that's exactly what I'm looking for. Thanks. – Bjarke H. Roune Jul 05 '11 at 23:44
  • 2
    By the way, the fact that the standard has no notion of "stack overflow" allows the compiler to perform aggressive tail-call optimization. (see e.g. http://stackoverflow.com/questions/5493688/stack-overflow-error-or-exception/) – Matteo Italia Jul 06 '11 at 00:19
  • If you read further, there's nothing in that section on the stack. That's a bit cheap since the standard doesn't mention the stack. However, Annex B places no restrictions on the number of recursive calls or on the amount of memory that can be allocated by automatic variables. Good thing that, because such limits are beyond the control of the compiler. They are emplaced by the OS and by evil system administrators who have set the stack limit too low. – David Hammen Jul 06 '11 at 01:19
  • 1
    The standard does not mention the stack because the stack is as much part of the standard as vtables (or... as little). The standard defines _features_ that the compiler must somehow implement, such as variables being cleaned up as they go out of scope, and functions returning, possibly after recursion, to where they were called. It _incidentially_ happens that a stack is well suited for these things (like vtables are _incidentially_ well suited for virtual inheritance), and therefore all known compilers use stacks, but that's just coincidence, and an (unimportant) implementation detail. – Damon Jul 06 '11 at 11:48
4

Behavior is undefined because the Standard does not define what happens with a program that exceeds resource limits. Note that there are recommended limits in Annex B of the spec. That annex is non-normative though and an implementation can ignore that annex, including having different limits than specified there. In 1.4 [intro.compliance], the spec says

If a program contains no violations of the rules in this International Standard, a conforming implementation shall, within its resource limits, accept and correctly execute that program.

There is nothing that says what shall happen with a program that contains no violation of the rules in the IS but that can't be accepted and correctly executed within the resource limits of the implementation. Hence behavior is undefined for such a case.

Johannes Schaub - litb
  • 496,577
  • 130
  • 894
  • 1,212
1

A stack overflow is breaking the protection mechanism that the operating system has in place. It is not a feature of the language as all machine executable code will have this same protection.

If you want to catch this particular error, you'll need to write operating system specific code. On Linux, for example, you'll need to catch a SIGSEGV (segmentation fault) signal. However, note that this could also be raised by a NULL pointer deference, or any other memory protection issues, not just stack overflow.

Not sure about Windows, OSX or mobile devices.

Mark
  • 768
  • 5
  • 12
  • 1
    On top of being an OS feature it is also something that impacts the observable behavior of a C++ program. So it is both something to do with C++ and something to do with the OS. As an example, I've gotten an exception in Java on stack overflow, so some other languages do define stack overflow. – Bjarke H. Roune Jul 05 '11 at 23:43
  • @Bjarke: I don't think it does impact the observable behavior of the program. I mean, obviously if the program unexpectedly terminates then you can observe that has happened, you sure won't observe the rest of the output. But we don't say that Windows Task Manager renders an implementation non-conformant because you can kill a running process, and I don't think the arbitrary actions of the stack-monitor are really all that different form the arbitrary actions of the user, as far as the standard is concerned. It's beyond the scope of the standard when and why an OS terminates a process. – Steve Jessop Jul 05 '11 at 23:54
1

What happens on stack overflow is extremely system-dependent (both CPU and OS, and sometimes compiler because it's up to the compiler to insert stack probes and other mechanisms for safely extending the stack), so it's impossible to mandate a particular response; the best that could be done would be to suggest responses that would be preferable if the target platform allows it. Most don't; while there is a reasonable way to handle heap overflow, a stack overflow handler (a) is likely to be invoked when the stack is in an inconsistent state, with a partially constructed stack frame on it, and (b) is likely to involve invoking a handler... which requires stack space for the interrupt frame. POSIX specifies a sigaltstack() mechanism, but it too has restrictions, and ANSI C C/C++ can't reasonably depend on POSIX compliance.

geekosaur
  • 59,309
  • 11
  • 123
  • 114