4 ms·

I just rewrite the stack function to use heap (eg, a queue) instead of stack.

by zandorg 15y ago

jmaygarden 15y ago
That sounds very inefficient given that every processor of which I am familiar has built-in support for a stack. Could you elaborate a bit more on your approach?
- Someone 15y ago
  For the curious: typically, pure RISC CPUs will have 'support for a stack' in the sense that it is not too hard to implement Algol-like languages on them, but not a stack proper. For example, neither PowerPC nor MIPS have designated stack pointer registers. As a consequence, they do not have a 'return from subroutine' instruction, they do not have pop or push, etc. ABIs will define a stack pointer, but if you control the hardware, you can use any register you want, none at all, have separate data and return address stacks, etc. Also, for a truly stackless CPU, look at system 370 (and, I guess, most other machines predating Algol)
ajross 15y ago
The application in question disallows heap usage. In "no runtime errors allowed" environment like this, everything is pre-allocated. This is easy for data structures (though it gets hairy once the usages start overlapping). This including the stack, which is hard to prove bounds for with traditional tools. So the author wrote some scripts to parse the disassembly.
- icefox 15y ago
  What about having the heap allocation actually use the stack?
  - stygianguest 15y ago
    In safety critical applications everything is very conservative by necessity: they are complicated systems consisting of many parts, ensuring correctness requires a rigorous workflow and complete toolchain. They involve not just multiple people but whole industries (think automotive). Most innovations fail because they do not integrate in the existing chain. Radical change can be accepted if, and only if it has extreme potential (orders of magnitude), because the existing methods are continously improved by small steps as well.
  - rcfox 15y ago
    That kind of defeats the purpose. Heap allocation is meant for objects that persist for the long-term. Stack allocation is meant for short-term storage, and anything that is allocated on the stack is lost when the function returns.
    - apaprocki 15y ago
      You can always allocate stack space (static or dynamic with alloca()) in main() before kicking off the application.
      - ajross 15y ago
        In which case it's isomorphic to a static memory block (albeit one with non-zero initialization costs), so what would the point be?
        icefox 15y ago
        Well the whole article seemed silly after he said this: "First of all, you can't use heap - not when you're in orbit. Why? Because quite simply, if you do use heap, and malloc returns null... what do you do? You can't ask the user for help" This is the OOM problem and is highly dependent upon the kernel you are using. Not bringing the kernel into the discussion means that the discussion is just silly. There is not much of a point to putting the heap in the stack as you said, but hey like the author we are just getting some ideas out there without bringing up the kernel.
        ttsiodras 15y ago
        I think you misinterpreted the article: the target is not Linux/x86, its a custom board with the SPARC/Leon processor running a custom embedded OS (RTEMS), launched in space :-) The article is just an example of the notions used, and how objdump can be used to enforce them. Linux is used simply for demonstration purposes. In your average PC with Linux/x86, it is clear that you fear neither stack nor heap error - you just restart the app :-)

I just rewrite the stack function to use heap (eg, a queue) instead of stack.

by zandorg 15y ago

I just rewrite the stack function to use heap (eg, a queue) instead of stack.

That sounds very inefficient given that every processor of which I am familiar has built-in support for a stack. Could you elaborate a bit more on your approach?

Someone 15y ago
For the curious: typically, pure RISC CPUs will have 'support for a stack' in the sense that it is not too hard to implement Algol-like languages on them, but not a stack proper. For example, neither PowerPC nor MIPS have designated stack pointer registers. As a consequence, they do not have a 'return from subroutine' instruction, they do not have pop or push, etc. ABIs will define a stack pointer, but if you control the hardware, you can use any register you want, none at all, have separate data and return address stacks, etc. Also, for a truly stackless CPU, look at system 370 (and, I guess, most other machines predating Algol)

ajross 15y ago

The application in question disallows heap usage. In "no runtime errors allowed" environment like this, everything is pre-allocated. This is easy for data structures (though it gets hairy once the usages start overlapping). This including the stack, which is hard to prove bounds for with traditional tools. So the author wrote some scripts to parse the disassembly.

icefox 15y ago
What about having the heap allocation actually use the stack?
- stygianguest 15y ago
  In safety critical applications everything is very conservative by necessity: they are complicated systems consisting of many parts, ensuring correctness requires a rigorous workflow and complete toolchain. They involve not just multiple people but whole industries (think automotive). Most innovations fail because they do not integrate in the existing chain. Radical change can be accepted if, and only if it has extreme potential (orders of magnitude), because the existing methods are continously improved by small steps as well.
- rcfox 15y ago
  That kind of defeats the purpose. Heap allocation is meant for objects that persist for the long-term. Stack allocation is meant for short-term storage, and anything that is allocated on the stack is lost when the function returns.
  - apaprocki 15y ago
    You can always allocate stack space (static or dynamic with alloca()) in main() before kicking off the application.
    - ajross 15y ago
      In which case it's isomorphic to a static memory block (albeit one with non-zero initialization costs), so what would the point be?
      - icefox 15y ago
        Well the whole article seemed silly after he said this: "First of all, you can't use heap - not when you're in orbit. Why? Because quite simply, if you do use heap, and malloc returns null... what do you do? You can't ask the user for help" This is the OOM problem and is highly dependent upon the kernel you are using. Not bringing the kernel into the discussion means that the discussion is just silly. There is not much of a point to putting the heap in the stack as you said, but hey like the author we are just getting some ideas out there without bringing up the kernel.
        ttsiodras 15y ago
        I think you misinterpreted the article: the target is not Linux/x86, its a custom board with the SPARC/Leon processor running a custom embedded OS (RTEMS), launched in space :-) The article is just an example of the notions used, and how objdump can be used to enforce them. Linux is used simply for demonstration purposes. In your average PC with Linux/x86, it is clear that you fear neither stack nor heap error - you just restart the app :-)