4

Maybe a naive question, but...

Confirm or deny:

The existence of memory for objects/variables of automatic and static storage duration is determined compile-time and there is absolutely zero chance that the program will fail runtime because there wasn't enough memory for an automatic object.

Naturally, when the constructor of an automatic object performs dynamic allocations and such allocation fails, we consider this to be a failure on dynamic allocation, and not automatic.

Armen Tsirunyan
  • 130,161
  • 59
  • 324
  • 434
  • While it can be confirmed at compile time for static objects, it cannot be done for automatic ones, because it depends on program logic. – ruslik Dec 07 '10 at 17:25
  • The way this question is worded sure sounds like homework/exam question, but I can't believe someone with 8k rep would be asking SO to do his homework. :) I'm curious where it came from though. – R.. GitHub STOP HELPING ICE Dec 07 '10 at 17:26
  • @R.. It came like this: When you try to allocate an automatic array which is too large you get a compile error, but when you try to allocate a large dynamic array you get a runtime error. So I thought, is it possible that I get a runtime error for the former case even if the compilation succeeds :) – Armen Tsirunyan Dec 07 '10 at 17:29
  • @Armen: do you expect compile error for this: `int f(){int t=f();};`? – ruslik Dec 07 '10 at 17:34
  • @ruslik: No, I most certainly do not. Though I will most likely get a warning – Armen Tsirunyan Dec 07 '10 at 17:36
  • @Armen: well, in simple cases compiler is able to avoid recursive calls. But when the recursion depth is not known at compile time, it won't be able to warn you. Also, in many cases the compiler won't even know the stack size. – ruslik Dec 07 '10 at 17:42

6 Answers6

13

Automatic allocation can certainly fail - this is usually known as a stack overflow. You see this quite often when someone tries to have a vary large array as a local variable. Unbounded (or not-bounded-enough) recursion can also cause this.

What you can't really do in a platform independent way is detect automatic allocation failure and handle it.

Michael Burr
  • 333,147
  • 50
  • 533
  • 760
  • "Detect automatic allocation failure and handle it" and this includes that you can't portably predict it. The program `int main() { int a = 1; int b = 2; return a + b;}` wouldn't be strictly conforming, since it relies on behavior that can vary between implementations (specifically, that there's enough stack available for two ints), except that formally it isn't varying behavior, because the standard doesn't mention the issue at all. Instead, it's beyond the scope of the standard whether any program works, aborts somehow at runtime, or trashes the heap. – Steve Jessop Dec 07 '10 at 17:45
13

Two words : Stack Overflow. :P

Prasoon Saurav
  • 91,295
  • 49
  • 239
  • 345
4

On systems with overcommit (e.g. Linux in the default configuration), it's even possible for objects of static storage duration to result in failure at runtime. At program startup, these objects will exist in either copy-on-write zero-pages (if they were uninitialized) or copy-on-write mappings of the on-disk executable file. Upon the first attempt to write to them, a page fault will happen and the kernel will make a local modifiable copy for your process. If the kernel was careless and did not reserve as much memory as it committed to the process, this could fail, and the result will be the dreaded OOM-killer.

No robust system has this problem, and the Linux behavior can be fixed by:

echo "2" > /proc/sys/vm/overcommit_memory
R.. GitHub STOP HELPING ICE
  • 208,859
  • 35
  • 376
  • 711
  • 1
    +1: Nonstandard behavior, brought to you by Linux! Thank you for making it impossible to create a conforming C implementation using default settings. *Bill installs BSD. – Billy ONeal Dec 07 '10 at 19:23
  • I'm pretty sure overcommit is traditional BSD behavior too, but I may be wrong. I just don't know the different BSD's well enough to comment so I didn't mention them. – R.. GitHub STOP HELPING ICE Dec 07 '10 at 20:02
2

Not true. An automatic allocation can cause a stack overflow, which causes instant process termination on most architectures/platforms of which I am aware.

Also, it's possible the program cannot allocate enough space for your static variables from the underlying platform, in which case the program will still fail, but it will fail before main is called.

Billy ONeal
  • 104,103
  • 58
  • 317
  • 552
  • If you're lucky it causes instant termination. If you're unlucky, it clobbers other portions of memory and gives the attacker root. :-) Fortunately the latter only happens in practice if you allocate insanely large (many kb) objects on the stack, but unsafe use of C99 VLA's can lead to this. – R.. GitHub STOP HELPING ICE Dec 07 '10 at 17:19
  • @R. Hmm.... not sure how other platforms handle this. On Win32 at least it terminates the process. On other boxes it might not. – Billy ONeal Dec 07 '10 at 17:20
  • @Billy: if each call only increases stack usage by a few kb, you'll hit a guard page and the process will get terminated. But what if a single call grows the stack by 2gb? Unless the compiler generates special code to check for this (and slows down all sane functions that don't need it) the stack pointer will just end up in the middle of some other memory, and your function will happily clobber that memory. – R.. GitHub STOP HELPING ICE Dec 07 '10 at 17:46
  • @R..: I think that technically it would only have to slow down functions which in total move the stack pointer by more than the size of the guard region (presuming that the compiler knows that, or perhaps the page size as a minimum), or which use VLAs, `alloca`, or similar. One could argue that such functions aren't entirely sane to begin with, or anyway that a performance hit on those things (by default, could be disabled by a compiler option) is worth it given how tricky they are to use safely. – Steve Jessop Dec 07 '10 at 18:15
  • Indeed. I think the best way is: whenever moving the stack pointer by more than `PAGE_SIZE`, move it in increments of `PAGE_SIZE` and write one word after each step. Then you're guaranteed to hit a guard page. – R.. GitHub STOP HELPING ICE Dec 07 '10 at 18:22
  • Although come to think of it, it depends too on the calling convention. If you can make a function call without touching stack, and don't touch stack in the function, but do move the sp, then a series of such calls could each move the sp by a "small" amount, adding up to enough to escape the guard region, then finally call something which goes boom. So there might also need to be a performance hit on functions which move the sp and call something else without touching the stack at all, if that's possible on a given system. – Steve Jessop Dec 07 '10 at 18:24
  • @R..: agreed about the technique to implement it. Alternative would be to have some internal means for the compiler to directly examine the state of the stack (so if it knows there's half a meg available, no need to hit every few kb), but that barely seems worth it unless you're doing really big amounts, and will have a cost for everything unless you already have some globally-accessible structure hanging about that can store a pointer to the end of the stack (kernel thread data or whatnot). – Steve Jessop Dec 07 '10 at 18:27
  • As long as function calls push a return address onto the stack, your issue of "small" amounts adding up is a non-issue. And I don't see how any implementation could handle more then a small finite (i.e. 1 step) level of nested function calls without touching the stack. As for the compiler generating code to examine the state of the stack, I **really** don't like unnecessary cross-dependency between compiler/linker/crt/libc/kernel/etc., especially when the purported benefits are marginal and only benefit code of dubious quality. – R.. GitHub STOP HELPING ICE Dec 07 '10 at 18:38
  • @R. You'd hit the guard page regardless of how the memory got hit. I don't see what the actual function call has to do with anything. – Billy ONeal Dec 07 '10 at 19:25
  • @R..: assuming all functions store their return address in the same place with respect to local variables. If one function stores its link register "above" a local array, then calls a function which stores a local array "above" anything that it actually touches (including its own link register if it makes further calls), then perhaps each function could only move the stack by half the size of guard region (+ delta), but nothing in the guard region would be touched since the guard region contains only the two arrays. So my "series" of calls is 2. – Steve Jessop Dec 08 '10 at 22:52
  • My "alternative" was based on a particular system which didn't have virtual memory and hence didn't use guard pages at all, but the compiler emitted code at function entry to do a stack check and call the kernel to extend the stack if necessary. The stack was a linked list of blocks, so "extend the stack" means move to a new block. Unusual case, I agree that it's not preferred, and possibly not relevant since of course in the presence of virtual memory the usual way is for the kernel to catch a hardware exception at the end of the currently-mapped stack region, and map in more physical RAM. – Steve Jessop Dec 08 '10 at 22:57
0

Simple counterexample:

#include <string.h>

int main()
{
    int huge[0x1FFFFFFF]; // Specific size doesn't matter;
                          // it just has to be bigger than the stack.

    memset(huge, 0, sizeof(huge) / sizeof(int));

    return 0;
}
nmichaels
  • 49,466
  • 12
  • 107
  • 135
  • Stack frame size is usually unlimited. Total size of the stack itself though, is usually the limiting factor. – Billy ONeal Dec 07 '10 at 17:10
  • @Armen: It should compile, but fail spectacularly at runtime. (Though it's possible the compiler looked at it and said "Are you loony?") If you try to compile this on a 32 bit machine it will fail because 2 billion integers is larger than the entire memory space of the machine (by about 2x). – Billy ONeal Dec 07 '10 at 17:12
  • @Armen: There, now it will compile all by itself. – nmichaels Dec 07 '10 at 17:13
  • @Billy: Hey, you're right. I forgot that I was using a 64-bit machine. – nmichaels Dec 07 '10 at 17:14
  • @R: Whoops, you're right. No change in the results of course. That's the trouble with writing incorrect programs. – nmichaels Dec 07 '10 at 17:26
-1

Example:

#include <iostream>

using namespace std;

class A
{
public:
    A() { p = new int[0xFFFFFFFF]; }

private:
    int* p;
};

static A g_a;

int main()
{
    cout << "Why do I never get called?" << endl;
}
Zac Howland
  • 15,777
  • 1
  • 26
  • 42
  • 1
    You missed the last sentence of the OP's question. "Naturally, when the constructor of an automatic object performs dynamic allocations and such allocation fails, we consider this to be a failure on dynamic allocation, and not automatic." EDIT: And `using namespace std;` needs to die! :P – Billy ONeal Dec 07 '10 at 17:13
  • `using namespace std;` in simple examples is hardly a problem. It makes the example more readable than having `std::` everywhere. Granted, in this example, it doesn't really matter since I'm only using 1 `cout` statement (and one that never gets run since the failure happens before it). Additionally, his question was regarding creation of static variables. I used `new`, but you could just as easily created the member variable as `int p[0x7FFFFFFF]` to get the same effect. In either case, it results in a stack overflow. – Zac Howland Dec 07 '10 at 17:20
  • @Zac: 1. I think it makes code *less* readable. When you're calling the standard library, it should be obvious at the call site. 2. No, neither the member variable nor the call to `new` result in a stack overflow. The first case will probably fail because the static storage space will be exhausted. The call to `new` fails because the heap is exhausted. Neither allocation touches the stack. Ever. – Billy ONeal Dec 07 '10 at 19:35
  • @Billy 1. That is a religious discussion that could go on until Judgement Day, so suffice it to say, to each their own. 2. You forget the full text of the stack overflow error: stack overruns heap. That is, if you allocate too much heap space, it will intersect your stack space (same with the static storage space), thus, in either case it results in the same problem: you are allocating too much memory in any given pot of memory and corrupting the other pots. – Zac Howland Dec 08 '10 at 15:15
  • @Zac: That's simply not true. The simplification "stack grows one way, heap grows the other" is not true on most real machines, because most real machines have virtual memory. Yes, you've got memory bounds being overrun, but that does not make it a stack overflow. Only automatic variables are stored on the stack, and you have no automatic variables there. – Billy ONeal Dec 08 '10 at 15:23
  • Also, w.r.t. `using namespace std;`: http://www.parashift.com/c++-faq-lite/coding-standards.html#faq-27.5 and http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-a-bad-practice-in-c – Billy ONeal Dec 08 '10 at 16:08
  • @Billy: As I stated, the `using namespace std;` directive in implementation files is a religious argument and frankly, it isn't one I really care enough about to bother debating. I find it useful when giving simple examples to use it instead of typing `std::` everywhere. The Parashift article says it best IMO: "Just remember that you are part of a team, so make sure you use an approach that is consistent with the rest of your organization." – Zac Howland Dec 08 '10 at 20:27