• Re: Has "stack overflow" specified behavior?

    From Bonita Montero@21:1/5 to All on Sun Dec 12 09:52:43 2021
    Am 12.12.2021 um 09:42 schrieb wij:
    void t() {
    int a;
    ++a;
    t();
    };

    int main()
    {
    t();
    }

    ---
    Has "stack overflow" specified behavior?

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From wij@21:1/5 to All on Sun Dec 12 00:42:51 2021
    void t() {
    int a;
    ++a;
    t();
    };

    int main()
    {
    t();
    }

    ---
    Has "stack overflow" specified behavior?

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From red floyd@21:1/5 to Bonita Montero on Sun Dec 12 12:59:32 2021
    On 12/12/2021 12:52 AM, Bonita Montero wrote:
    Am 12.12.2021 um 09:42 schrieb wij:
    void t() {
       int a;
       ++a;
       t();
    };

    int main()
    {
      t();
    }

    ---
    Has "stack overflow" specified behavior?

    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.

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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Paavo Helde@21:1/5 to All on Mon Dec 13 01:51:13 2021
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Juha Nieminen@21:1/5 to Paavo Helde on Mon Dec 13 05:48:06 2021
    Paavo Helde <eesnimi@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).)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bo Persson@21:1/5 to Juha Nieminen on Mon Dec 13 10:44:36 2021
    On 2021-12-13 at 06:48, Juha Nieminen wrote:
    Paavo Helde <eesnimi@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).)

    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?

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Richard Damon@21:1/5 to Bo Persson on Mon Dec 13 07:47:05 2021
    On 12/13/21 4:44 AM, Bo Persson wrote:
    On 2021-12-13 at 06:48, Juha Nieminen wrote:
    Paavo Helde <eesnimi@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).)

    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?



    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From wij@21:1/5 to Bo Persson on Mon Dec 13 04:44:17 2021
    On Monday, 13 December 2021 at 17:44:58 UTC+8, 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?

    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).)
    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?

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Manfred@21:1/5 to wij on Mon Dec 13 17:08:22 2021
    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".

    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").

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From James Kuyper@21:1/5 to Bo Persson on Mon Dec 13 12:13:29 2021
    On 12/13/21 4:44 AM, Bo Persson wrote:
    On 2021-12-13 at 06:48, Juha Nieminen wrote:
    Paavo Helde <eesnimi@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Manfred@21:1/5 to Juha Nieminen on Mon Dec 13 17:23:24 2021
    On 12/13/2021 6:48 AM, Juha Nieminen wrote:
    Paavo Helde <eesnimi@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From =?UTF-8?B?w5bDtiBUaWli?=@21:1/5 to james...@alumni.caltech.edu on Mon Dec 13 12:05:59 2021
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Tim Rentsch@21:1/5 to wij on Mon Dec 13 13:13:42 2021
    wij <wyniijj@gmail.com> writes:

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

    int main()
    {
    t();
    }

    ---
    Has "stack overflow" specified behavior?

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Tim Rentsch@21:1/5 to Manfred on Mon Dec 13 13:50:31 2021
    Manfred <noname@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Tim Rentsch@21:1/5 to Paavo Helde on Mon Dec 13 14:16:05 2021
    Paavo Helde <eesnimi@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From wij@21:1/5 to Tim Rentsch on Mon Dec 13 15:07:54 2021
    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 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?

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Keith Thompson@21:1/5 to wij on Mon Dec 13 15:55:16 2021
    wij <wyniijj@gmail.com> writes:
    void t() {
    int a;
    ++a;
    t();
    };

    int main()
    {
    t();
    }

    ---
    Has "stack overflow" specified behavior?

    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.Thompson+u@gmail.com
    Working, but not speaking, for Philips
    void Void(void) { Void(); } /* The recursive call of the void */

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Keith Thompson@21:1/5 to Keith Thompson on Mon Dec 13 15:58:41 2021
    Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
    wij <wyniijj@gmail.com> writes:
    void t() {
    int a;
    ++a;
    t();
    };

    int main()
    {
    t();
    }

    ---
    Has "stack overflow" specified behavior?

    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.

    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.

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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From jameskuyper@alumni.caltech.edu@21:1/5 to All on Mon Dec 13 17:11:56 2021
    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:
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From jameskuyper@alumni.caltech.edu@21:1/5 to All on Mon Dec 13 19:00:40 2021
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From =?UTF-8?B?w5bDtiBUaWli?=@21:1/5 to james...@alumni.caltech.edu on Mon Dec 13 23:03:19 2021
    On Tuesday, 14 December 2021 at 05:00:53 UTC+2, james...@alumni.caltech.edu wrote:
    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.

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bonita Montero@21:1/5 to All on Tue Dec 14 08:32:06 2021
    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 ?

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bonita Montero@21:1/5 to All on Tue Dec 14 08:33:15 2021
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From David Brown@21:1/5 to Bonita Montero on Tue Dec 14 09:13:24 2021
    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
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Paavo Helde@21:1/5 to All on Tue Dec 14 10:32:00 2021
    14.12.2021 00:16 Tim Rentsch kirjutas:
    Paavo Helde <eesnimi@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]"

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Juha Nieminen@21:1/5 to David Brown on Tue Dec 14 10:09:44 2021
    David Brown <david.brown@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From wij@21:1/5 to Keith Thompson on Tue Dec 14 01:41:14 2021
    On Tuesday, 14 December 2021 at 07:55:35 UTC+8, Keith Thompson wrote:
    wij <wyn...@gmail.com> writes:
    void t() {
    int a;
    ++a;
    t();
    };

    int main()
    {
    t();
    }

    ---
    Has "stack overflow" specified behavior?
    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 */

    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).

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Richard Damon@21:1/5 to Bonita Montero on Tue Dec 14 07:49:23 2021
    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.

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Richard Damon@21:1/5 to Bonita Montero on Tue Dec 14 07:59:56 2021
    On 12/14/21 2:33 AM, 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.


    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Scott Lurndal@21:1/5 to Richard Damon on Tue Dec 14 14:23:26 2021
    Richard Damon <Richard@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));
    }

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Manfred@21:1/5 to Tim Rentsch on Tue Dec 14 16:32:22 2021
    On 12/13/2021 10:50 PM, Tim Rentsch wrote:
    Manfred <noname@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.

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Alf P. Steinbach@21:1/5 to Richard Damon on Tue Dec 14 16:16:46 2021
    On 14 Dec 2021 13:49, Richard Damon wrote:

    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.

    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.

    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Ben Bacarisse@21:1/5 to Juha Nieminen on Tue Dec 14 16:14:50 2021
    Juha Nieminen <nospam@thanks.invalid> writes:

    David Brown <david.brown@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Ben Bacarisse@21:1/5 to David Brown on Tue Dec 14 16:10:41 2021
    David Brown <david.brown@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Alf P. Steinbach@21:1/5 to James Kuyper on Tue Dec 14 16:19:51 2021
    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 <eesnimi@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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From James Kuyper@21:1/5 to Alf P. Steinbach on Tue Dec 14 11:33:25 2021
    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 <eesnimi@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bonita Montero@21:1/5 to All on Tue Dec 14 17:38:29 2021
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Scott Lurndal@21:1/5 to Bonita Montero on Tue Dec 14 17:09:59 2021
    Bonita Montero <Bonita.Montero@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.

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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bonita Montero@21:1/5 to All on Tue Dec 14 18:39:37 2021
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From David Brown@21:1/5 to Keith Thompson on Tue Dec 14 20:15:06 2021
    On 14/12/2021 19:52, Keith Thompson wrote:
    David Brown <david.brown@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Keith Thompson@21:1/5 to David Brown on Tue Dec 14 10:52:35 2021
    David Brown <david.brown@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 (The_Other_Keith) Keith.S.Thompson+u@gmail.com
    Working, but not speaking, for Philips
    void Void(void) { Void(); } /* The recursive call of the void */

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Keith Thompson@21:1/5 to Scott Lurndal on Tue Dec 14 11:01:42 2021
    scott@slp53.sl.home (Scott Lurndal) writes:
    Bonita Montero <Bonita.Montero@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.

    [...]

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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Chris M. Thomasson@21:1/5 to Ben Bacarisse on Tue Dec 14 15:23:37 2021
    On 12/14/2021 8:14 AM, Ben Bacarisse wrote:
    Juha Nieminen <nospam@thanks.invalid> writes:

    David Brown <david.brown@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.)


    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);
    }
    }
    ______________________

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Jorgen Grahn@21:1/5 to Juha Nieminen on Wed Dec 15 23:27:14 2021
    On Mon, 2021-12-13, Juha Nieminen wrote:
    Paavo Helde <eesnimi@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 .

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From David Brown@21:1/5 to Jorgen Grahn on Thu Dec 16 08:37:07 2021
    On 16/12/2021 00:27, Jorgen Grahn wrote:
    On Mon, 2021-12-13, Juha Nieminen wrote:
    Paavo Helde <eesnimi@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.)


    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.)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Tim Rentsch@21:1/5 to wij on Thu Dec 16 05:53:30 2021
    wij <wyniijj@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Tim Rentsch@21:1/5 to Paavo Helde on Thu Dec 16 07:42:52 2021
    Paavo Helde <eesnimi@osa.pri.ee> writes:

    14.12.2021 00:16 Tim Rentsch kirjutas:

    Paavo Helde <eesnimi@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]"

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From wij@21:1/5 to Tim Rentsch on Thu Dec 16 08:34:44 2021
    On Thursday, 16 December 2021 at 21:53:48 UTC+8, Tim Rentsch wrote:
    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.

    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').

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Keith Thompson@21:1/5 to wij on Thu Dec 16 12:17:13 2021
    wij <wyniijj@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.

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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From =?UTF-8?B?w5bDtiBUaWli?=@21:1/5 to Tim Rentsch on Thu Dec 16 14:14:31 2021
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From wij@21:1/5 to Keith Thompson on Thu Dec 16 13:38:27 2021
    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.
    --
    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 */

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Keith Thompson@21:1/5 to wij on Thu Dec 16 14:15:38 2021
    wij <wyniijj@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.

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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Chris Vine@21:1/5 to Tim Rentsch on Fri Dec 17 01:07:55 2021
    On Thu, 16 Dec 2021 07:42:52 -0800
    Tim Rentsch <tr.17687@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Ben Bacarisse@21:1/5 to Chris Vine on Fri Dec 17 01:28:52 2021
    Chris Vine <chris@cvine--nospam--.freeserve.co.uk> writes:

    On Thu, 16 Dec 2021 07:42:52 -0800
    Tim Rentsch <tr.17687@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.

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

    --
    Ben.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Tim Rentsch@21:1/5 to wij on Thu Dec 16 20:10:39 2021
    wij <wyniijj@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Tim Rentsch@21:1/5 to Chris Vine on Thu Dec 16 19:54:17 2021
    Chris Vine <chris@cvine--nospam--.freeserve.co.uk> writes:

    On Thu, 16 Dec 2021 07:42:52 -0800
    Tim Rentsch <tr.17687@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.

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Tim Rentsch@21:1/5 to Tiib on Thu Dec 16 20:20:44 2021
    Tiib <ootiib@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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Chris Vine@21:1/5 to Tim Rentsch on Fri Dec 17 10:06:23 2021
    On Thu, 16 Dec 2021 19:54:17 -0800
    Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
    Chris Vine <chris@cvine--nospam--.freeserve.co.uk> writes:

    On Thu, 16 Dec 2021 07:42:52 -0800
    Tim Rentsch <tr.17687@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.

    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.

    Good point!

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From =?UTF-8?B?w5bDtiBUaWli?=@21:1/5 to Tim Rentsch on Fri Dec 17 08:46:09 2021
    On Friday, 17 December 2021 at 06:21:00 UTC+2, Tim Rentsch wrote:
    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.

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)