[dataflow]

I think the parent comment was about malloc not being real-time? Not about storage space.

Though I do wonder why there can't be a form of malloc that allocates in a stack like fashion in real time to satisfy the formal verifier?

[kllrnohj]

Real time also generally means your input sizes are bounded and known, otherwise the algorithm itself isn't realtime and malloc isn't the reason why.

But strictly speaking the only problem is a malloc/free that can lock (you can end up with priority inversion). So a lock-free malloc would be realtime just fine, it doesn't have to be stack growth only.

[dataflow]

> Real time also generally means your input sizes are bounded and known, otherwise the algorithm itself isn't realtime and malloc isn't the reason why.

I think you meant to say something else? Real-time is a property of the system indicating a constraint on the latency from the input to the output—it doesn't constrain the input itself. (Otherwise even 'cat' wouldn't be real-time!)

[ordu]

If your input is not bounded you can't know in advance the time needed to process it. In other word you cannot be realtime.

`cat` can be realtime, but only by fixing the size of its internal buffer where it reads to and writes from. In this case it can in theory bound the time needed to process the fixed block of input.

But if for some reason `cat` tried to read/write by lines of unknown in advance size, it would fail to be realtime.

[dataflow]

I think we're not disagreeing on the actual constraints, but the terminology. The "internal buffer" is not part of the system's "input". It's part of the system's "state".

[kllrnohj]

We're talking about function inputs, not system inputs.

[dataflow]

Real-time is a property of the whole system though (?) not individual functions. But even if you want to reframe it to be about functions, small input is neither necessary nor sufficient for it being "real time". Like your function might receive an arbitrarily large n-element array a[] and just return a[a[n-1]], and it would be constant time. Again, the size is the simply not the correct property to look at.

[remexre]

> Though I do wonder why there can't be a form of malloc that allocates in a stack like fashion in real time

I think that's basically what the LLVM SafeStack pass does -- stack variables that might be written out of bounds are moved to a separate stack so they can't smash the return address.

[jcelerier]

how would you implement that in the face of multiple threads? you can't use TLS as it will have initialize your stack on first access of your malloc_stack in a given thread, which may or may not be safe to use in real-time-ish-contexts (I think it's definitely not on Windows, not sure on Linux)

[dataflow]

> how would you implement that in the face of multiple threads?

I imagine you could you allocate it at the same time as you allocate the thread's own stack?