Has "stack overflow" specified behavior?

[wij]

void t() {
int a;
++a;
t();
};

int main()
{
t();
}

---
Has "stack overflow" specified behavior?

[Bonita Montero]

If you're lucky a stack overflow even won't happen because the com-
piler will detect the tail-recursion and convert it into an iteration.

[red floyd]

Not to mention the potential UB with the use-before-initialization of
the ++a; statement.

[Paavo Helde]

No. Stack overflow is arguably the least specified behavior of them all.
The stack size is extremely limited (few MB), compared to the RAM
amounts current computers have (tens of GB). There is no
standard-defined way to detect stack overflow, not to speak about
handling it. That's one reason why using stack-allocated things like
std::array needs special care, especially when writing libraries (which
need to execute in a stack of unknown size and fill-up).

There are some implementation-defined ways though to survive stack
overflows, but it's not so easy. You cannot continue the program if
there is no more stack space, so the only way is to throw an exception.
Alas, there is no "throw" statement in the code, so this would be an
"asynchronous" exception appearing at a pretty random place in the code,
meaning that the compiler must cope with such exceptions, which may
easily slow down the whole program (witness the /EHa compiler option in
MSVC).

BTW, your example code is not guaranteed to cause stack overflow, it
might go into an infinite loop instead because of tail recursion, or
become a zero op by optimizing the whole t() function away, either as UB
or as a code with no effect.

[Juha Nieminen]

Paavo Helde <ees...@osa.pri.ee> wrote:
> No. Stack overflow is arguably the least specified behavior of them all.
> The stack size is extremely limited (few MB), compared to the RAM
> amounts current computers have (tens of GB). There is no
> standard-defined way to detect stack overflow, not to speak about
> handling it.

That made me think: Why has neither the C nor the C++ standardization
committees ever thought of adding a standard library utility to get
the current amount of free stack space?

Sure, perhaps in some operating systems this isn't something that
programs can get, but the function in question could be optional in
that sense. For example it could return -1 to indicate "this operation
is not supported", else a non-negative value to indicate the amount
of free stack space. This could give programs at least the opportunity
to gracefully do something if running out of stack space. I think this
could be useful especially in programs that need to be as stable and
secure as possible.

(In fact, getting the amount of free (physical) RAM available to the
process could also be useful, for similar reasons. It could behave
in the same way: -1 if the operation is for some reason not supported,
else the amount of free RAM (not counting swap).)

[Bo Persson]

This would be of very limited use. The result of a call from one thread
wouldn't be valid long, if the other threads allocate and free memory
already while the result is returned.

It is similar to filesystem::exists("path"). If you get a true or false
back, how long is the result valid? Nanoseconds?

[wij]

If such a function is useful, the duration the value valid is not a problem.
The only useful cases I have are when implementing 'synchronized' thread
(not sure about the name) or the function algorithm uses stack heavily, e.g.
when the size of an object is significantly large.

[Richard Damon]

Actually, most threading libraries creat threads with a FIXED sized
stack (specified in the create call or it uses a default), and that
space is all reserved for the thread stack.

Only the main thread tends to have an expandable stack, which often
grows into the heap, so only the main thread would be affected by other
threads activities.

I suspect that part of the issue is that while it would normally be
possible to compute how much address space is available for the stack,
it can be more complicated to figure out if you can map usable ram into
that address space, and with the Linux over-commit issue, the straight
answer might easily be not available, or expensive to compute.

Also, this is something easy for a system to add as a system defined
function, that works for it. The fact that this isn't commonly available
seems to be a sign that it isn't really easy to provide what might be
needed, or it isn't really needed.

[Manfred]

Putting apart the specific example, the standard describes the behavior
of the abstract machine only, but Appendix B refers to constraints posed
by actual implementations, and that includes the "nesting levels of
compound statements" (which in turn include function bodies).
So, what you call stack overflow (an expression not found in the
standard) is in fact a possible violation of a constraint posed by the
implementation.
As a kind of constraint violation this leads to UB - specifically I'd
consider this under n4860 p4.1 clause (2.3) "If a program contains a
violation of a rule for which no diagnostic is required, this document
places no requirement on implementations with respect to that program".

With respect to the example given, n4860 p6.9.2.2 gives explicit
permission to an implementation to remove the loop, and compile the
whole program as a no-op (ref. "observable behavior").

[Manfred]

On 12/13/2021 6:48 AM, Juha Nieminen wrote:
> Paavo Helde <ees...@osa.pri.ee> wrote:
>> No. Stack overflow is arguably the least specified behavior of them all.
>> The stack size is extremely limited (few MB), compared to the RAM
>> amounts current computers have (tens of GB). There is no
>> standard-defined way to detect stack overflow, not to speak about
>> handling it.
>
> That made me think: Why has neither the C nor the C++ standardization
> committees ever thought of adding a standard library utility to get
> the current amount of free stack space?

The more general answer is that the standard (both C and C++) describes
the behavior of an "abstract machine", and the requirement for actual
conformant implementations is to produce the same "observable behavior"
as the abstract machine.
The standard does not even mandate a stack [*]; it specifies the
language rules for function calls, scope, local variables etc. all of
which is commonly implemented via a memory stack, but that's the
implementation, not the abstract machine.
The standard then connects back to the real world in Appendix B, where
it says that limitations of finite systems may result in program
constraints that should be documented by the implementation.
In this perspective such constraints fall under the "implementation
defined" category.

>
> Sure, perhaps in some operating systems this isn't something that
> programs can get, but the function in question could be optional in
> that sense. For example it could return -1 to indicate "this operation
> is not supported", else a non-negative value to indicate the amount
> of free stack space. This could give programs at least the opportunity
> to gracefully do something if running out of stack space. I think this
> could be useful especially in programs that need to be as stable and
> secure as possible.
>
> (In fact, getting the amount of free (physical) RAM available to the
> process could also be useful, for similar reasons. It could behave
> in the same way: -1 if the operation is for some reason not supported,
> else the amount of free RAM (not counting swap).)

[*] The standard talks a.o. about "stack unwinding", thus referring to
the common concept of a stack, but only to describe the process of
destructing objects with automatic storage when leaving their scope. So,
it's a concept related with scoping and lifetime, not with the stack
memory structure.

[James Kuyper]

On 12/13/21 4:44 AM, Bo Persson wrote:

> On 2021-12-13 at 06:48, Juha Nieminen wrote:
>> Paavo Helde <ees...@osa.pri.ee> wrote:
>>> No. Stack overflow is arguably the least specified behavior of them all.
>>> The stack size is extremely limited (few MB), compared to the RAM
>>> amounts current computers have (tens of GB). There is no
>>> standard-defined way to detect stack overflow, not to speak about
>>> handling it.
>>
>> That made me think: Why has neither the C nor the C++ standardization
>> committees ever thought of adding a standard library utility to get
>> the current amount of free stack space?

A key factor in that decision is the fact that neither the C nor the C++
standard ever talks about the stack space, a fact that allows either
language to be implemented on systems where the concept of "stack" is
meaningless.
On operating systems where the concept is meaningful, there often is a
way to conduct such a query. For instance, on Unix-like systems, there's
getrlimit(RLIMIT_STACK, &rlim).

,,,

>> (In fact, getting the amount of free (physical) RAM available to the
>> process could also be useful, for similar reasons. It could behave
>> in the same way: -1 if the operation is for some reason not supported,
>> else the amount of free RAM (not counting swap).)
>
> This would be of very limited use. The result of a call from one thread
> wouldn't be valid long, if the other threads allocate and free memory
> already while the result is returned.
>
> It is similar to filesystem::exists("path"). If you get a true or false
> back, how long is the result valid? Nanoseconds?

There's an important difference: as a matter of the policies you use for
managing a filesystem (rather than anything enforced by the operating
system), it is not only possible, but commonplace, to be certain that a
given file, if present, will remain in existence long enough to do
whatever it is you want to do with it.
That's not the case with the amount of free stack space.

[Öö Tiib]

On Monday, 13 December 2021 at 19:13:58 UTC+2, james...@alumni.caltech.edu wrote:
> On 12/13/21 4:44 AM, Bo Persson wrote:
> > On 2021-12-13 at 06:48, Juha Nieminen wrote:
> >> Paavo Helde <ees...@osa.pri.ee> wrote:
> >>> No. Stack overflow is arguably the least specified behavior of them all.
> >>> The stack size is extremely limited (few MB), compared to the RAM
> >>> amounts current computers have (tens of GB). There is no
> >>> standard-defined way to detect stack overflow, not to speak about
> >>> handling it.
> >>
> >> That made me think: Why has neither the C nor the C++ standardization
> >> committees ever thought of adding a standard library utility to get
> >> the current amount of free stack space?
>
> A key factor in that decision is the fact that neither the C nor the C++
> standard ever talks about the stack space, a fact that allows either
> language to be implemented on systems where the concept of "stack" is
> meaningless.

That feels like quite odd argument. How can that distract anyone from
fact that every implementation has to have some kind of storage
that is used for storing objects with automatic storage duration? Neither
standard denies that it has to exist nor that it is potentially limited.
Avoiding naming it with some shorter name does not make it
disappear from abstract machine. It may run out of available space
and the standards avoid providing any ways to estimate that space
or to handle that event.

[Tim Rentsch]

The expression '++a' tries to read an uninitialized variable.
After correcting for that oversight (for example, by giving a
value to 'a' at its declaration by 'int a = 0;'), the program has
defined behavior. To be more specific, each of the operations
asked for in the program has a well-defined description of what
is to happen in the abstract machine, which means the program as
a whole has defined behavior.

Note that this conclusion is about what will take place in the
/abstract/ machine, and not about what occurs if and when the
program is run in an /actual/ machine. The C++ standard
explicitly lets executing a program in an actual machine off the
hook for running out of any kind of limited resource, including
but not limited to "stack space". Section 4.1 paragraph 2.1 of
n4860 says this:

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

So even though the program has defined behavior, it may very
well fail due to running out of stack space when executed.
Moreover that applies to all programs, for any kind of
resource the implementation might depend on.

Short summary: the program (not counting the uninitialized
access) has defined behavior, but may fail because of stack
overflow during an actual execution.

[Tim Rentsch]

Manfred <non...@add.invalid> writes:

> On 12/12/2021 9:42 AM, wij wrote:
>
>> void t() {
>> int a;
>> ++a;
>> t();
>> };
>>
>> int main()
>> {
>> t();
>> }
>>
>> ---
>> Has "stack overflow" specified behavior?
>
> Putting apart the specific example, the standard describes the
> behavior of the abstract machine only, but Appendix B refers to
> constraints posed by actual implementations, and that includes the
> "nesting levels of compound statements" (which in turn include
> function bodies).
> So, what you call stack overflow (an expression not found in the
> standard) is in fact a possible violation of a constraint posed by the
> implementation.
> As a kind of constraint violation this leads to UB - specifically I'd
> consider this under n4860 p4.1 clause (2.3) "If a program contains a
> violation of a rule for which no diagnostic is required, this document
> places no requirement on implementations with respect to that
> program".

First, I think you mean Annex B, not Appendix B.

Second, Annex B never uses the word 'constraint'.

Third, Annex B is informative, not normative. Nothing it says can
change the rules governing the C++ language. (Side note: Annex B
itself says in the last sentence of paragraph 2:

However, these quantities are only guidelines and do not
determine compliance.

End side note.)

The program shown above (after fixing the problem of reading an
uninitialized variable) has defined behavior, not undefined
behavior. An execution of the program in an actual machine may
fail due to running out of stack space (or any other resource)
per section 4.1 paragraph 2.1. Despite that, what happens in the
abstract machine is well-defined, and so the program has only
defined behavior, and no undefined behavior.

[Tim Rentsch]

It's important to distinguish the two realms of abstract machine
and actual machine. In the abstract machine, the program shown

above (after fixing the problem of reading an uninitialized

variable) does have a well-defined specification, and the program
as a whole has defined behavior. Whether a program has defined
behavior or undefined behavior is determined solely by what goes
on in the abstract machine (which may depend on values read from
a file or other input device, etc, but still the question is to
be answered considering only what happens in the abstract
machine, with reference to any actual machine). Everything the
program does has a well-defined specification, and so the program

has only defined behavior, and no undefined behavior.

In an actual machine, an implementation is obliged to carry out
the abstract semantics only to the extent that the execution
does not exceed the implementation's "resource limits", which
might be anything at all, including stack space. Once such a
resource limit is exceeded, the implementation has no further
obligations, and may abort, or whatever. But that isn't the
same as undefined behavior, which depends solely on what the
standard says about operations in the abstract machine.

[wij]

If the concept of abstract (ideal) machine is used (the 1st time I heard this
term in use). The infinite recursive call should be defined as it is (never
return, or infinite loop except semantics 'optimized' to differ), all functions
within should be carried out successfully. But, for this ideal to be anything
reasonable, there should at least one machine that can execute the program
correctly.
If this is accepted, what should this 'actual machine' do with the infinite
recursive call?

[Keith Thompson]

The standard does not specify what happens when a resource limit is
exceeded. In my opinion that matches the standard's definition of
"undefined behavior" (behavior that is not defined).

Is the variable `a` intended to track the depth of the recursion? It
doesn't. A new instance of `a` is created every time t is called. You
didn't initialize `a`, but if you initialized it to 0 then `++a` would
simply set it to 1.

If you made `a` static, it would count the depth of the recursion -- and
you'd have undefined behavior after the value of `a` reaches INT_MAX.

With `a` defined as you did here, there's a distinct instance of `a` for
each call to t, and each instance has its own distinct address, a value
of type int*. There can be at most 2**(CHAR_BIT * sizeof (int*))
distinct int* values. If you never refer to the value or address of `a`,
an optimizing compiler is likely to eliminate it and change the
recursive call to a loop, but that doesn't apply in the abstract
machine. See N1570 5.1.2.3 "Program execution":

The semantic descriptions in this International Standard describe
the behavior of an abstract machine in which issues of optimization
are irrelevant.

In the abstract machine, each instance of `a` occupies sizeof (int) bytes
and has a unique address of type int*. After optimization, `a` might not
exist.

--
Keith Thompson (The_Other_Keith) Keith.S.T...@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

[Keith Thompson]

My apologiess, I didn't notice which newsgroup I was in and gave a C
answer. But the C++ standard also discusses the "abstract machine" in
section 4.6 [intro.execution], with a very similar meaning.

[james...@alumni.caltech.edu]

On Monday, December 13, 2021 at 3:06:11 PM UTC-5, Öö Tiib wrote:
> On Monday, 13 December 2021 at 19:13:58 UTC+2, james...@alumni.caltech.edu wrote:

...

> > A key factor in that decision is the fact that neither the C nor the C++
> > standard ever talks about the stack space, a fact that allows either
> > language to be implemented on systems where the concept of "stack" is
> > meaningless.
> That feels like quite odd argument. How can that distract anyone from
> fact that every implementation has to have some kind of storage
> that is used for storing objects with automatic storage duration? Neither
> standard denies that it has to exist nor that it is potentially limited.
> Avoiding naming it with some shorter name does not make it
> disappear from abstract machine. It may run out of available space
> and the standards avoid providing any ways to estimate that space
> or to handle that event.

Because calling it a stack carries implications that a typical hardware
stack must be involved, using memory that's completely distinct from the
heap, with each function call's local variables being pushed onto the stack
immediately between the local variables for the calling routine, and the
local variables for the routines it calls.
There are real world machines with no hardware stack. Some of them
dynamically allocate something called "activation records" to store such
objects, the same way they allocate memory when malloc() is called. While
the function call hierarchy means that memory used for objects with
automatic storage duration has LIFO semantics, the activation record for a
calling function need not be anywhere near the activation record for the
called function. And there's no need for such memory to be allocated and
deallocated strictly in LIFO order. The activation record for a given function
call must be allocated some time before the function call starts executing,
but it needn't be allocated immediately before it. An activation record must
not be deallocated until after the function call ends, but it needn't be
deallocated immediately afterward.
For all those reasons, calling it a stack would be a bad idea, because it
would give too many false impressions about what is required.

[Öö Tiib]

OK. However consecutive elements being adjacent in memory is not implied
property of "stack" in C++. Any attempt to treat adjacently defined
objects with automatic storage as adjacent in memory is undefined
behavior. Also the LIFO container adapter std::stack uses
std::deque as default underlying container and so lacks that property.
So while you are correct that typical hardware stack has certain handy
properties ... those are commonly out of reach of C++ programmer unless
implementation takes to define additional guarantees as extension.

[Bonita Montero]

Am 13.12.2021 um 13:47 schrieb Richard Damon:

> Actually, most threading libraries creat threads with a FIXED sized
> stack (specified in the create call or it uses a default), and that
> space is all reserved for the thread stack.

How would an implementation of a variable stack space look like when
the stack can't be moved because of pointers inside the stack-frames ?

[Bonita Montero]

Am 13.12.2021 um 18:13 schrieb James Kuyper:

> A key factor in that decision is the fact that neither the C nor the C++
> standard ever talks about the stack space, a fact that allows either
> language to be implemented on systems where the concept of "stack" is
> meaningless.

Every language that allows recursions has a stack.
And both C and C++ allow recursions.

[David Brown]

As so often happens, your views are coloured by your "all the world is
an x86 running Windows" experience.


Certainly stacks are the usual way to implement such languages.

But they are not the only way - AFAIK there have been computers that
used a linked list of local data frames rather than a stack. There are
also systems with two stacks - one for data, one for return addresses.
And there are lots of small systems implementing C that only have very
inefficient implementations for recursive functions because of poor
hardware support for stacks, and do not use a stack for code unless a
function actually is recursive.

C (and to a lesser extent C++) is designed to be implementable on a very
wide range of systems. Adding features that are specific to particular
kinds of implementations limits that flexibility. It might be worth
doing, of course - some kinds of systems could be viewed as outdated, or
we could simply say that they only implement a subset of the language
standard. (As an example, with C++20, and C2x, two's complement signed
integer representation is now blessed as the only option.) But these
things are not to be taken lightly or arbitrarily.

[Paavo Helde]

14.12.2021 00:16 Tim Rentsch kirjutas:
> Paavo Helde <ees...@osa.pri.ee> writes:
>
>> 12.12.2021 10:42 wij kirjutas:
>>
>>> void t() {
>>> int a;
>>> ++a;
>>> t();
>>> };
>>>
>>> int main()
>>> {
>>> t();
>>> }
>>

>> BTW, your example code is not guaranteed to cause stack overflow, it
>> might go into an infinite loop instead because of tail recursion, or
>> become a zero op by optimizing the whole t() function away, either
>> as UB or as a code with no effect.
>
> It's important to distinguish the two realms of abstract machine
> and actual machine. In the abstract machine, the program shown
> above (after fixing the problem of reading an uninitialized
> variable) does have a well-defined specification, and the program
> as a whole has defined behavior. Whether a program has defined
> behavior or undefined behavior is determined solely by what goes
> on in the abstract machine (which may depend on values read from
> a file or other input device, etc, but still the question is to
> be answered considering only what happens in the abstract
> machine, with reference to any actual machine). Everything the
> program does has a well-defined specification, and so the program
> has only defined behavior, and no undefined behavior.

You might be right in that after fixing the uninitialized memory reading
bug the program would not contain UB. Nevertheless, the standard gives
explicit permission to a C++ implementation to optimize away such code
with no observable side effects, making this whole program a non-op
instead of an infinite CPU or memory eater:

"6.9.2.2 Forward progress [intro.progress]
1 The implementation may assume that any thread will eventually do one
of the following:
(1.1) — terminate,
(1.2) — make a call to a library I/O function,
(1.3) — perform an access through a volatile glvalue, or
(1.4) — perform a synchronization operation or an atomic operation.
[Note: This is intended to allow compiler transformations such as
removal of empty loops, even when termination cannot be proven. —end note]"

[wij]

The 'a' was added when typing to remove 'optimization' answer, not succeeded.
Sorry it caused too(?) many attention (but, answers to that part might be helpful
to other readers).

[Juha Nieminen]

David Brown <david...@hesbynett.no> wrote:
>> Every language that allows recursions has a stack.
>> And both C and C++ allow recursions.
>
> As so often happens, your views are coloured by your "all the world is
> an x86 running Windows" experience.
>
> Certainly stacks are the usual way to implement such languages.

I think in this context a distinction should be made between the concept
of a "stack" in the algorithm / computer science sense, and a "stack" in
the sense of a particular implementation of one.

In the computer science sense a "stack" is pretty much a synonym for
"a LIFO data container". However, how exactly that LIFO container is
implemented is not set in stone.

Recursion does indeed require a stack by necessity. However, any
dynamic LIFO data container will do for this, and thus no specific
implementation is imposed.

[Richard Damon]

It doesn't.

The Thread APIs I know create a FIXED size stack for a new thread and it
can not be changed/moved after the thread is started.

The fact that there can exist pointers to data on the stack (possible on
the stack) is one big reason for this limitation.

Just like if you use realloc you need to be careful of dangling
references to the old buffer, trying to move a thread stack is a hard,
likely impossible, problem.

The main thread stack can be expandable, as it often has a special
relationship to the heap, so you can trade memory between the stack and
the heap. There is normally only one such special location.

I suppose you could grossly over-allocate the stack space for a thread
and then create some sort of auxiliary heap at the end of it, and trade
of use of that heap with stack space for that thread.

[Richard Damon]

It may have a concetual stack, but doesn't need an actual hardware stack.

I have used a processor where a call instruction placed the return
address at the targeted address, then started execution the instruction
therafter.

If the function was marked as being recursive, then the beginning of the
function would allocate a block of memory (like with malloc), copy this
address, and any other local variables previously saved into that block,
and the start the function. To return, those values were copied back,
the block released and then a jump indirect the calling address was
performed.

No stack in sight. Only something that was in effect a linked list,
which can emmulate a stack.

[Scott Lurndal]

Richard Damon <Ric...@Damon-Family.org> writes:
>
>On 12/14/21 2:32 AM, Bonita Montero wrote:
>> Am 13.12.2021 um 13:47 schrieb Richard Damon:
>>
>>> Actually, most threading libraries creat threads with a FIXED sized
>>> stack (specified in the create call or it uses a default), and that
>>> space is all reserved for the thread stack.
>>
>> How would an implementation of a variable stack space look like when
>> the stack can't be moved because of pointers inside the stack-frames ?
>>
>
>It doesn't.
>
>The Thread APIs I know create a FIXED size stack for a new thread and it
>can not be changed/moved after the thread is started.
>
>The fact that there can exist pointers to data on the stack (possible on
>the stack) is one big reason for this limitation.
>
>Just like if you use realloc you need to be careful of dangling
>references to the old buffer, trying to move a thread stack is a hard,
>likely impossible, problem.

We did that in a bare-metal hypervisor last decade:

/**
* Initialize the per-core DVMM stack.
*
* Allocate a pages for the stack and copy the stack
* content from the bootstrap stack to the newly allocated stack,
* adjusting any values on the bootstrap stack that appear to be
* addresses of objects in the boot stack (primarily the saved rbp
* register values).
*
* Since the stack grows towards lower addresses, we'll allocate a
* guard area (of #c_as::GUARD_PAGES in length) immediately before the
* per-core stack. The guard area is implemented by unmapping the
* virtual address(es) corresponding to the guard area. If a stack
* push or call op causes the stack to enter this region,
* a \#PF exception will be thrown.
*/
void
c_core::initialize_stack(void)
{
uintptr_t offset;
MFN mfn;

mfn = node->local_mem()->allocate_contig(
BYTE_COUNT_TO_PAGES(EXCEPTION_STACK_SIZE),
0, socket_num, c_page_allocator::LOC_FIRST);
ASSERT(mfn != ENOMFN);
exception_stack = (uintptr_t)ma_to_ptr(mfn.to_ma());

mfn = node->local_mem()->allocate_contig(
BYTE_COUNT_TO_PAGES(STACK_SIZE) + GUARD_PAGES,
0, socket_num, c_page_allocator::LOC_FIRST);
// CPU stack pages should not come out of export mem
ASSERT(mfn != ENOMFN);
stack = (uintptr_t)ma_to_ptr(mfn.to_ma());

unmap(PAGE_NUMBER(stack), GUARD_PAGES);
stack += GUARD_PAGES * PAGE_SIZE;

ASSERT((ptrdiff_t)(init_stack_top - init_stack) == (ptrdiff_t)STACK_SIZE);

memcpy((void *)stack, init_stack, STACK_SIZE);

//
// Make sure any stack pointers on the stack get adjusted too.
//
offset = get_rsp() - (uintptr_t)init_stack;

for(uintptr_t sp = stack + offset;
sp < (stack + STACK_SIZE);
sp += sizeof(uintptr_t)) {
uintptr_t qword = *(uintptr_t *)sp;

if ((qword >= (uintptr_t)init_stack)
&& (qword <= (uintptr_t)init_stack_top)) {
*(uintptr_t *)sp = stack + (qword - (uintptr_t)init_stack);
}
}
set_rsp(stack + offset);
set_rbp(stack + (get_rbp() - (uintptr_t)init_stack));
}

[Alf P. Steinbach]

It's technically possible to use (that is, for the compiler to support)
a linked list based stack, and that could be preferable for real coroutines.

AFAIK no compiler linked list stack by default, but apparently gcc
supports, or at least did support when one used the "gold linker", a
scheme called a "split stack".

I'm not sure but googling it now and looking at the first hit it seems
that the compiler generates additional stack checking instructions that
allocates and links up a new stack part when the current is too small.
I.e. this is not a linked list of stack frames but a linked list of
stack parts.

https://gcc.gnu.org/wiki/SplitStacks

---

With 64-bit addressing and a reasonably low number of threads I guess
one could in principle just allocate a largish address range for each
stack, and expand the backing in terms of real memory pages, as needed,
perhaps with the need detected via a guard page to avoid overhead of
stack size checking code in every function.

E.g. in Windows pages are managed via `VirtualAlloc` function & friends.

But I haven't heard of such scheme being used.


- Alf

[Alf P. Steinbach]

On 13 Dec 2021 18:13, James Kuyper wrote:
> On 12/13/21 4:44 AM, Bo Persson wrote:
>> On 2021-12-13 at 06:48, Juha Nieminen wrote:
>>> Paavo Helde <ees...@osa.pri.ee> wrote:
>>>> No. Stack overflow is arguably the least specified behavior of them all.
>>>> The stack size is extremely limited (few MB), compared to the RAM
>>>> amounts current computers have (tens of GB). There is no
>>>> standard-defined way to detect stack overflow, not to speak about
>>>> handling it.
>>>
>>> That made me think: Why has neither the C nor the C++ standardization
>>> committees ever thought of adding a standard library utility to get
>>> the current amount of free stack space?
>
> A key factor in that decision is the fact that neither the C nor the C++
> standard ever talks about the stack space, a fact that allows either
> language to be implemented on systems where the concept of "stack" is
> meaningless.

The C++ standard talks about e.g. "stack unwinding", which contradicts
the assertion the neither standard uses the word (with this meaning).

There can be no systems where the concept of "stack" is meaningless,
which contradicts the second assertion.

Perhaps you meant to write something else.


[snip]


Cheers, - Alf

[Manfred]

Yes, Annex B

>
> Second, Annex B never uses the word 'constraint'.

Clause 2: "The limits may constrain quantities that include those
described below or others"

>
> Third, Annex B is informative, not normative. Nothing it says can
> change the rules governing the C++ language.

It is informative because it cannot mandate constraints that are
inherently implementation dependent: see the word "may" above. However,
whenever such constraints are posed by the implementation (i.e. always
for any real implementation) they are obviously effective.

(Side note: Annex B
> itself says in the last sentence of paragraph 2:
>
> However, these quantities are only guidelines and do not
> determine compliance.
>
> End side note.)

The "guideline" part is about the list of constrained quantities. Any
given physical implementation "may constrain quantities that include
those described below or others", which obviously leaves implementations
free choice of which limits they pose (and it couldn't be any different).

>
> The program shown above (after fixing the problem of reading an
> uninitialized variable) has defined behavior, not undefined
> behavior. An execution of the program in an actual machine may
> fail due to running out of stack space (or any other resource)
> per section 4.1 paragraph 2.1. Despite that, what happens in the
> abstract machine is well-defined, and so the program has only
> defined behavior, and no undefined behavior.

I beg to differ.

[Ben Bacarisse]

David Brown <david...@hesbynett.no> writes:

> On 14/12/2021 08:33, Bonita Montero wrote:
>> Am 13.12.2021 um 18:13 schrieb James Kuyper:
>>
>>> A key factor in that decision is the fact that neither the C nor the C++
>>> standard ever talks about the stack space, a fact that allows either
>>> language to be implemented on systems where the concept of "stack" is
>>> meaningless.
>>
>> Every language that allows recursions has a stack.
>> And both C and C++ allow recursions.
>
> As so often happens, your views are coloured by your "all the world is
> an x86 running Windows" experience.
>
>
> Certainly stacks are the usual way to implement such languages.
>
> But they are not the only way - AFAIK there have been computers that
> used a linked list of local data frames rather than a stack.

IBM mainframes did this. The System 360 was the one knew. The modern
versions probably use the same plan, unless they are running a Unix
flavour.

--
Ben.

[Ben Bacarisse]

Juha Nieminen <nos...@thanks.invalid> writes:

> David Brown <david...@hesbynett.no> wrote:
>>> Every language that allows recursions has a stack.
>>> And both C and C++ allow recursions.
>>
>> As so often happens, your views are coloured by your "all the world is
>> an x86 running Windows" experience.
>>
>> Certainly stacks are the usual way to implement such languages.
>
> I think in this context a distinction should be made between the concept
> of a "stack" in the algorithm / computer science sense, and a "stack" in
> the sense of a particular implementation of one.

Yes, these are too often confused, which does not help the discussion.

> In the computer science sense a "stack" is pretty much a synonym for
> "a LIFO data container". However, how exactly that LIFO container is
> implemented is not set in stone.
>
> Recursion does indeed require a stack by necessity.

In the most general cases, yes, but some languages actually specify that
certain recursive calls will not use a new data frame. (The point being
that recursion does not always require a stack.)

--
Ben.

[James Kuyper]

On 12/14/21 10:19 AM, Alf P. Steinbach wrote:
> On 13 Dec 2021 18:13, James Kuyper wrote:
>> On 12/13/21 4:44 AM, Bo Persson wrote:
>>> On 2021-12-13 at 06:48, Juha Nieminen wrote:
>>>> Paavo Helde <ees...@osa.pri.ee> wrote:
>>>>> No. Stack overflow is arguably the least specified behavior of them all.
>>>>> The stack size is extremely limited (few MB), compared to the RAM
>>>>> amounts current computers have (tens of GB). There is no
>>>>> standard-defined way to detect stack overflow, not to speak about
>>>>> handling it.
>>>>
>>>> That made me think: Why has neither the C nor the C++ standardization
>>>> committees ever thought of adding a standard library utility to get
>>>> the current amount of free stack space?
>>
>> A key factor in that decision is the fact that neither the C nor the C++
>> standard ever talks about the stack space, a fact that allows either
>> language to be implemented on systems where the concept of "stack" is
>> meaningless.
>
> The C++ standard talks about e.g. "stack unwinding", which contradicts
> the assertion the neither standard uses the word (with this meaning).

You're right. While I know a lot about both standards, I tend to be more
familiar with the C standard (which quite literally never uses the word
stack) than about C++ (which says almost nothing about "the stack"), so
I overstated my case.

The term "stack unwinding" is italicized in C++ 14.3p1, an ISO
convention indicating that the sentence containing that italicized
phrase constitutes the official definition of that term. That sentence is
"As control passes from the point where an exception is thrown to a
handler, objects with automatic storage duration are destroyed by a
process, specified in this subclause, called stack unwinding."

Keep in mind that there's a general principle that applies to phrases
with a meaning defined by the standard: you cannot in general break them
up into individual words and attack separate meanings to those words.
For example, in C, a "null pointer constant" need not be a pointer, it
could be an integer constant with a value of 0. In C++, a "null pointer
constant" cannot be a pointer - no pointer expressions meet the
requirements.

Similarly, you cannot derive any information about "the stack" from the
definition provided by C++ section 14.3 for "stack unwinding". While
that definition goes into considerable detail about initialization and
destruction of C++ objects, and the order in which those things occur,
it says nothing about where those objects may be located.

C++ section 14.3 implies LIFO ordering of the construction and
destruction of objects, but it only constrains the order in which the
memory they reside in is allocated and deallocated, it doesn't determine
that order. The memory can be allocated at any time prior to
construction of the object, and deallocated at any time subsequent to
the destruction of the object - those actions need not occur in LIFO
order. I don't know of any specific reason why there would be any
benefit in allocating the memory any earlier than absolutely necessary,
nor for deallocating it any later than absolutely necessary, but I would
not recommend ruling out the possibility that there might be some
benefits from doing so. Regardless of whether or not there's any good
reason to do so, an implementation of C++ which chose to would not
qualify as non-conforming, at least, not for that reason.

> There can be no systems where the concept of "stack" is meaningless,
> which contradicts the second assertion.

I worded that badly, and apologize. It's not that the concept of a
"stack" is meaningless, C++ even provides std::stack<>.

My point was that the ideas that all computers must have a stack built
in, and that the rules for objects with automatic storage duration
mandate the use of that stack, are both incorrect.

[Bonita Montero]

Am 14.12.2021 um 09:13 schrieb David Brown:

> But they are not the only way - AFAIK there have been computers

> that used a linked list of local data frames rather than a stack....

That's also a stack.

[Scott Lurndal]

No, it's a linked list. Unordered and non-contiguous.

But then you're just arguing for the sake of argument.

[Bonita Montero]

Am 14.12.2021 um 18:09 schrieb Scott Lurndal:

>>> But they are not the only way - AFAIK there have been computers
>>> that used a linked list of local data frames rather than a stack....

>> That's also a stack.

> No, it's a linked list. Unordered and non-contiguous.

A linked list can also be a stack if you add and remove items
only at one end.

[Keith Thompson]

David Brown <david...@hesbynett.no> writes:
> On 14/12/2021 08:33, Bonita Montero wrote:
>> Am 13.12.2021 um 18:13 schrieb James Kuyper:
>>
>>> A key factor in that decision is the fact that neither the C nor the C++
>>> standard ever talks about the stack space, a fact that allows either
>>> language to be implemented on systems where the concept of "stack" is
>>> meaningless.
>>
>> Every language that allows recursions has a stack.
>> And both C and C++ allow recursions.
>
> As so often happens, your views are coloured by your "all the world is
> an x86 running Windows" experience.
>
> Certainly stacks are the usual way to implement such languages.
>
> But they are not the only way - AFAIK there have been computers that
> used a linked list of local data frames rather than a stack.

[...]

There are (at least) two distinct meanings of "stack".

One is a contiguous region of memory used to allocate memory for
function calls, growing in one direction in the address space and
shrinking in the other. Most C implementations do use a "stack"
in this sense, but the standard doesn't specify it.

Another is any data structure that supports LIFO allocation and
deallocation. *Every* C implementation has this kind of stack to
support the semantics of function calls, however it's implemented.

[Keith Thompson]

sc...@slp53.sl.home (Scott Lurndal) writes:
> Bonita Montero <Bonita....@gmail.com> writes:
>>Am 14.12.2021 um 09:13 schrieb David Brown:
>>
>>> But they are not the only way - AFAIK there have been computers
>>> that used a linked list of local data frames rather than a stack....
>>
>>That's also a stack.
>
> No, it's a linked list. Unordered and non-contiguous.

Unordered and non-contiguous *in memory*, but logically ordered.

As I and others have mentioned, the word "stack" can refer either to a
contiguous region of memory or to an arbitrary data structure managed in
a last-in first-out manner.

[...]

[David Brown]

On 14/12/2021 19:52, Keith Thompson wrote:
> David Brown <david...@hesbynett.no> writes:
>> On 14/12/2021 08:33, Bonita Montero wrote:
>>> Am 13.12.2021 um 18:13 schrieb James Kuyper:
>>>
>>>> A key factor in that decision is the fact that neither the C nor the C++
>>>> standard ever talks about the stack space, a fact that allows either
>>>> language to be implemented on systems where the concept of "stack" is
>>>> meaningless.
>>>
>>> Every language that allows recursions has a stack.
>>> And both C and C++ allow recursions.
>>
>> As so often happens, your views are coloured by your "all the world is
>> an x86 running Windows" experience.
>>
>> Certainly stacks are the usual way to implement such languages.
>>
>> But they are not the only way - AFAIK there have been computers that
>> used a linked list of local data frames rather than a stack.
> [...]
>
> There are (at least) two distinct meanings of "stack".
>
> One is a contiguous region of memory used to allocate memory for
> function calls, growing in one direction in the address space and
> shrinking in the other. Most C implementations do use a "stack"
> in this sense, but the standard doesn't specify it.
>
> Another is any data structure that supports LIFO allocation and
> deallocation. *Every* C implementation has this kind of stack to
> support the semantics of function calls, however it's implemented.
>

Agreed.

[Chris M. Thomasson]

Fwiw, when I write something that's recursive, I always end up thinking
about how to create an iterative version of it. Here is the iterative
version of a recursive fractal I created a while back:

https://pastebin.com/raw/0B7rNx9Z
______________________
// Fractal Parametric Wave Plotter
void ct_fwave_mpara(
ct::plot2d& plot,
unsigned int n,
ct_complex p0,
ct_complex p1,
unsigned int nr
) {
ct_complex dif = p1 - p0;
// Build the Fractal wave
ct_float abase = 1.0 / n;
ct_float abase_wave = CT_PI * 1 / n;
for (unsigned int i = 0; i < n; i++)
{
ct_float angle = abase * i;
ct_float angle_wave = abase_wave * i * nr;
ct_float y_temp = abs(sin(angle_wave)) * 1.0 / nr + (p0.imag()
+ (dif.imag() * angle));

// Fractal Wave High
ct_complex wp0 = {
p0.real() + (dif.real() * angle),
y_temp
};

// Fractal Wave Low
ct_complex wp1 = {
p0.real() + (dif.real() * angle),
-y_temp
};

plot.set_pixelf(wp0, CT_RGBF(1., 1., 0.));
plot.set_pixelf(wp1, CT_RGBF(0., 1., 1.));
}
}

// Fractal Parametric Wave Function
void ct_fwave(
ct::plot2d& plot,
unsigned int n,
ct_complex p0,
ct_complex p1,
unsigned int nr
) {
// For every level
for (unsigned int recur_i = 0; recur_i < n; ++recur_i)
{
// Plot the wave
ct_fwave_mpara(plot, 3072, p0, p1, nr);

// Compute next wave
nr = nr * (recur_i + 2);
}
}
______________________

[Jorgen Grahn]

On Mon, 2021-12-13, Juha Nieminen wrote:
> Paavo Helde <ees...@osa.pri.ee> wrote:
>> No. Stack overflow is arguably the least specified behavior of them all.
>> The stack size is extremely limited (few MB), compared to the RAM
>> amounts current computers have (tens of GB). There is no
>> standard-defined way to detect stack overflow, not to speak about
>> handling it.
>
> That made me think: Why has neither the C nor the C++ standardization
> committees ever thought of adding a standard library utility to get
> the current amount of free stack space?

This is not an answer but: I'd rather have a tool which could do
static analysis and come up with an upper limit to stack usage. (It
would have to give less useful answers if the program used recursion
or C VLAs, but that's ok.)

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[David Brown]

Such tools are available, and are not uncommon in embedded development
(where stacks are often /much/ smaller, and ram can be very limited).
There are lots of things that can make stack usage analysis difficult,
including threads, call-backs, and function pointers as well as the more
obvious points like recursion, alloca, or C VLA's.

gcc has some options for generating stack usage reports on functions, as
well as warnings for stack frames that grow too large and some run-time
stack checking. I haven't made any real use of these, so I can't say
how helpful they might be. (And I guess other compilers could have
similar features - gcc is just the one I know.)

[Tim Rentsch]

wij <wyn...@gmail.com> writes:

> On Tuesday, 14 December 2021 at 06:16:23 UTC+8, Tim Rentsch wrote:
>
>> Paavo Helde <ees...@osa.pri.ee> writes:
>>
>>> 12.12.2021 10:42 wij kirjutas:
>>>

>>>> void t() {
>>>> int a;
>>>> ++a;
>>>> t();
>>>> };
>>>>
>>>> int main()
>>>> {
>>>> t();
>>>> }
>>>>
>>>> ---
>>>> Has "stack overflow" specified behavior?
>>>

>>> No. Stack overflow is arguably the least specified behavior of them
>>> all. The stack size is extremely limited (few MB), compared to the
>>> RAM amounts current computers have (tens of GB). There is no
>>> standard-defined way to detect stack overflow, not to speak about

>>> handling it. That's one reason why using stack-allocated things
>>> like std::array needs special care, especially when writing
>>> libraries (which need to execute in a stack of unknown size and
>>> fill-up).
>>>
>>> There are some implementation-defined ways though to survive stack
>>> overflows, but it's not so easy. You cannot continue the program if
>>> there is no more stack space, so the only way is to throw an
>>> exception. Alas, there is no "throw" statement in the code, so this
>>> would be an "asynchronous" exception appearing at a pretty random
>>> place in the code, meaning that the compiler must cope with such
>>> exceptions, which may easily slow down the whole program (witness
>>> the /EHa compiler option in MSVC).

>>>
>>> BTW, your example code is not guaranteed to cause stack overflow, it
>>> might go into an infinite loop instead because of tail recursion, or
>>> become a zero op by optimizing the whole t() function away, either
>>> as UB or as a code with no effect.
>>
>> It's important to distinguish the two realms of abstract machine

>> and actual machine. In the abstract machine, the program shown

>> above (after fixing the problem of reading an uninitialized

>> variable) does have a well-defined specification, and the program
>> as a whole has defined behavior. Whether a program has defined
>> behavior or undefined behavior is determined solely by what goes
>> on in the abstract machine (which may depend on values read from
>> a file or other input device, etc, but still the question is to
>> be answered considering only what happens in the abstract
>> machine, with reference to any actual machine). Everything the

>> program does has a well-defined specification, and so the program

>> has only defined behavior, and no undefined behavior.

>> In an actual machine, an implementation is obliged to carry out
>> the abstract semantics only to the extent that the execution
>> does not exceed the implementation's "resource limits", which
>> might be anything at all, including stack space. Once such a
>> resource limit is exceeded, the implementation has no further
>> obligations, and may abort, or whatever. But that isn't the
>> same as undefined behavior, which depends solely on what the
>> standard says about operations in the abstract machine.
>
> If the concept of abstract (ideal) machine is used (the 1st time I
> heard this term in use).

The term "abstract machine" comes from the C++ standard (and
originally from the C standard). It is not an ideal machine,
just an abstract machine, meaning there are some details it
doesn't pin down.

> The infinite recursive call should be defined as it is (never
> return, or infinite loop except semantics 'optimized' to differ),
> all functions within should be carried out successfully.

Because the abstract machine is abstract, it doesn't have any
notion of running out of memory. The semantic descriptions
simply say another object instance is created, without any
concern about where memory for that object might come from.

> But, for this ideal to be anything reasonable, there should at
> least one machine that can execute the program correctly.

Again, the abstract machine is only abstract, not ideal. Part of
the point of considering an abstract machine is the abstract
machine doesn't need to consider some things that actual machines
do. It isn't possible to make an actual machine that faithfully
models the abstract machine, in much the same way that it isn't
possible to make an actual machine that faithfully models a
Turing machine. Actual machines are always bounded; Turing
machines, and the abstract machine, are potentially unbounded.

> If this is accepted, what should this 'actual machine' do with the
> infinite recursive call?

The premise that there is some actual machine that faithfully
models the abstract machine is wrong. Since there is no such
actual machine, there is no answer to the question of what it
should do. Any "actual machine" that can in fact be made will
at some point just run out of memory.

[Tim Rentsch]

> (1.1) - terminate,
> (1.2) - make a call to a library I/O function,
> (1.3) - perform an access through a volatile glvalue, or
> (1.4) - perform a synchronization operation or an atomic operation.

> [Note: This is intended to allow compiler transformations such as

> removal of empty loops, even when termination cannot be proven. -end
> note]"

Yes, I noticed that before. I didn't comment on it because, one,
it strikes me as incidental to the main question, and two, if we
change the example just slightly

void t() {
volatile int a = 0;

++a;
t();
};

int main()
{
t();
}

then the program cannot be optimized into nothingness, so we
still have the question of how an implementation is obliged to
treat this program. And I think the answer is the same, that
implementations are obliged to try to carry it out faithfully but
are allowed to fail when they run out of memory. Failure here
isn't the same as undefined behavior, because up to the point of
actually running out of memory everything is fine as far as the
abstract semantics are concerned. To say that another way, it is
a well-established point that undefined behavior is allowed to
affect things "in the past", but here that freedom is not
granted. The presence of volatile reads and writes means that
there are other consequences that could be observed, such as
program running time, so there isn't the same kind of freedom
as would be allowed for undefined behavior.

[wij]

Thanks for the explanation, I thought "abstract machine" is a new
invention to explain the language.

By the way, I though the 'stack' still must exist no matter how it is
implemented. Because the process of RAII/function call and the
'auto' (old name) variables are mostly efficient in the stack.
These all added to be most efficient in one stack (or 'primary stack').

[Keith Thompson]

wij <wyn...@gmail.com> writes:
[...]

> By the way, I though the 'stack' still must exist no matter how it is
> implemented. Because the process of RAII/function call and the
> 'auto' (old name) variables are mostly efficient in the stack.
> These all added to be most efficient in one stack (or 'primary stack').

It depends on what you mean by "stack".

Most C++ implementations use a "stack" in the sense of a contiguous
region of memory managed via a pointer to the "top".

A contiguous memory "stack" (which is not required by the standard) is
the most common way to implement the abstract last-in first-out
semantics of function calls. There are implementations (at least for C,
and probably for C++) that do something similar to a malloc call to
allocate storage for a new function call.

[wij]

If so, something should still be remained in the main stack for the tracking
to work. Each function can have its own stack, that stack can be reallocated,
but the address value can't change. In all, these maneuvers are opaque to the user.
The user code just don't assume the amount of stack space acquired is the whole
thing. Nothing too significantly changes from the user's point of view. IOW, getting
the amount of stack space (from API) seems still significant, just not common.

[Öö Tiib]

On Thursday, 16 December 2021 at 15:53:48 UTC+2, Tim Rentsch wrote:
>
> Because the abstract machine is abstract, it doesn't have any
> notion of running out of memory. The semantic descriptions
> simply say another object instance is created, without any
> concern about where memory for that object might come from.

Lack of capability of operations that provide storage to fail does
not follow from abstract machine being abstract.
The very same abstract machine has malloc function that can
fail to provide storage. About malloc we also have no
concern where the memory might come from so that is utterly
orthogonal point.

[Keith Thompson]

wij <wyn...@gmail.com> writes:
> On Friday, 17 December 2021 at 04:17:31 UTC+8, Keith Thompson wrote:
>> wij <wyn...@gmail.com> writes:
>> [...]
>> > By the way, I though the 'stack' still must exist no matter how it is
>> > implemented. Because the process of RAII/function call and the
>> > 'auto' (old name) variables are mostly efficient in the stack.
>> > These all added to be most efficient in one stack (or 'primary stack').
>> It depends on what you mean by "stack".
>>
>> Most C++ implementations use a "stack" in the sense of a contiguous
>> region of memory managed via a pointer to the "top".
>>
>> A contiguous memory "stack" (which is not required by the standard) is
>> the most common way to implement the abstract last-in first-out
>> semantics of function calls. There are implementations (at least for C,
>> and probably for C++) that do something similar to a malloc call to
>> allocate storage for a new function call.
>

> If so, something should still be remained in the main stack for the
> tracking to work. Each function can have its own stack, that stack can
> be reallocated, but the address value can't change. In all, these
> maneuvers are opaque to the user. The user code just don't assume the
> amount of stack space acquired is the whole thing. Nothing too
> significantly changes from the user's point of view. IOW, getting the
> amount of stack space (from API) seems still significant, just not
> common.

As I said, there are (at least) two very different meanings of the word
"stack". I can't tell which one you're using here.

[Chris Vine]

On Thu, 16 Dec 2021 07:42:52 -0800
Tim Rentsch <tr.1...@z991.linuxsc.com> wrote:
> Yes, I noticed that before. I didn't comment on it because, one,
> it strikes me as incidental to the main question, and two, if we
> change the example just slightly
>
> void t() {
> volatile int a = 0;
> ++a;
> t();
> };
>
> int main()
> {
> t();
> }
>
> then the program cannot be optimized into nothingness, so we
> still have the question of how an implementation is obliged to
> treat this program. And I think the answer is the same, that
> implementations are obliged to try to carry it out faithfully but
> are allowed to fail when they run out of memory.

Isn't overflow in signed integers still undefined behavior? If so
implementations can do whatever they want should they implement tail
call optimization and so overflow on the integer.

[Ben Bacarisse]

Optimising that tail call won't cause integer overflow. Optimisations
are obliged to preserve semantics!

--
Ben.

[Tim Rentsch]

There is one 'a' variable for each level of recursion. Each 'a'
starts at 0 and gets incremented to 1, stopping at that value
just before the recursive call. So none of the 'a' variables
ever overflows.

[Tim Rentsch]

wij <wyn...@gmail.com> writes:

[...]

> By the way, I though the 'stack' still must exist no matter how it

> is implemented. [...]

Some sort of machinery with stack-like behavior must be there, to
support recursive calls if nothing else. But there doesn't have
to be a "stack" in the sense of a fixed, contiguous region of
memory that is used exclusively for state local to each call of a
function. Other ways of providing function-local state have been
used, and depending on the operating environment they can be
practical, feasible, or even preferable.

[Tim Rentsch]

Tiib <oot...@hot.ee> writes:

> On Thursday, 16 December 2021 at 15:53:48 UTC+2, Tim Rentsch wrote:
>
>> Because the abstract machine is abstract, it doesn't have any
>> notion of running out of memory. The semantic descriptions
>> simply say another object instance is created, without any
>> concern about where memory for that object might come from.
>
> Lack of capability of operations that provide storage to fail does

> not follow from abstract machine being abstract. [...]

Yes, that was poor phrasing on my part. Because of the kinds of
semantic descriptions used in defining the abstract machine tend
to gloss over certain kinds of details, we may reasonably expect
that they don't take running out of memory into account. And
that is indeed the case in the C++ standard for function calls
and what happens with local variables. Section 6.9.1 paragraph 1
says this:

An instance of each object with automatic storage duration
(6.7.5.3) is associated with each entry into its block. Such
an object exists and retains its last-stored value during the
execution of the block and while the block is suspended [...]

There is no mention of any possibility of running out of memory.

[Chris Vine]

On Thu, 16 Dec 2021 19:54:17 -0800

Good point!

[Öö Tiib]

I agree. There are none defined ways for some operations like

char txt[100]{};

to fail because of lack of storage. Meanwhile somewhat equivalent

std::string str(100, 0);

can fail because of lack of storage. There std::allocator<char>
of that str can throw std::bad_alloc.
So IMHO the first definition of txt could also be defined
to throw std::bad_alloc (or something special like
std::stack_overflow) because of failing to complete.
That would not make the abstract machine less
abstract but just ... better designed.