79

I started developing software for real-time systems a few months ago in C for space applications, and also for microcontrollers with C++. There's a rule of thumb in such systems that one should never create heap objects (so no malloc/new), because it makes the program non-deterministic. I wasn't able to verify the correctness of this statement when people tell me that. So, Is this a correct statement?

The confusion for me is that as far as I know, determinism means that running a program twice will lead to the exact, same execution path. From my understanding this is an issue with multithreaded systems, since running the same program multiple times could have different threads running in different order every time.

The Quantum Physicist
  • 24,987
  • 19
  • 103
  • 189
  • 2
    It's not just about execution paths, but program state (physical, not just logical). If you do dynamic allocation the addresses of objects shift. – StoryTeller - Unslander Monica Sep 19 '17 at 10:38
  • 12
    Dynamic memory allocation and de-allocation suffers from the issue of memory fragmentation, which is not expected in real-time applications. – Gaurav Pathak Sep 19 '17 at 10:43
  • 1
    I have worked in real time safety critical system and in which there are some standards each adhere. For example in medical system they have different standards and in that they don't do dynamic memory allocation. – danglingpointer Sep 19 '17 at 10:47
  • 1
    Dynamic allocations are prone to many problems on the systems with very limited resources and run in the not hosted environment. Generally speaking - experience from large computer (like PC) programming is not very relevant to the RT or uC programming. – 0___________ Sep 19 '17 at 10:55
  • Btw, I'm not unhappy about not being able to use new/malloc. I'm just wondering about the reasons. You guys are giving me great arguments. Thanks! I'm interested in hearing more! – The Quantum Physicist Sep 19 '17 at 10:57
  • Another addon to my comment, this question will give your more insight about usage of heap in safety critical system, https://stackoverflow.com/questions/36618043/alternatives-to-dynamic-allocations-in-safety-critical-projects-c – danglingpointer Sep 19 '17 at 10:57
  • 24
    Basically it goes like this: PC programmers get taught to use malloc/new. They come to embedded systems where the heap doesn't make any sense whatsoever, because those are built with an entirely different architecture and mindset. PC programmer gets upset, this is not what they thought me in school! And I've been using the heap on PC for ages! PC programmer ignores everyone and goes to do heap allocation still. The program turns out as crap, full of bugs and bad performance. PC programmer gets fired. Embedded system programmer gets to take over the mess. Program gets re-written from scratch. – Lundin Sep 19 '17 at 11:08
  • You'll have a hard time doing something truly non-deterministic with a standard computer which is not defective. The reason is that great care is taken to reduce entropy in the critical parts (and make it other peoples' problem with large fans and fins). All randomness in a nominally working computer (including embedded systems) comes from the outside, e.g. through `/dev/random`. What your colleagues meant is behavior which violates timing or memory constraints in unexpected ways. Such behavior is (deterministically, but perhaps unexpectedly) triggered by (possibly non-deterministic) inputs. – Peter - Reinstate Monica Sep 19 '17 at 14:59
  • 11
    @PeterA.Schneider As a physicist who did a PhD in particle and atomic physics, it's already very difficult for me to draw the line between what's deterministic and what's non-deterministic in computers; this is because we're arguably living in a non-deterministic universe. I understand that my question can easily trigger a circular argument as whether anything is ever deterministic before calling it deterministic under certain assumptions. But the language use of determinism here is restricted to how computer-scientists use it, which is not practically related to real randomness in nature. – The Quantum Physicist Sep 19 '17 at 15:15
  • Well, my tongue-in-cheek comment does have a serious aspect, which Peter covered in his answer. The -- let's call it unpredicability -- of starting condition and inputs result in a perfectly deterministic program and machine running de-facto non-deterministically. The embedded system programming rules I encountered were designed to fail in a defined way: Statically allocate N items and go to a safe state if and when N is exceeded, instead of overwriting unpredictable memory at unpredictable times with unpredictable results -- all strictly deterministic, mind you ;-). – Peter - Reinstate Monica Sep 19 '17 at 15:39
  • @PeterA.Schneider I see, sure. I got your answer actually and all the answers together made me learn what computer guys mean when they talk about determinism (which is why I'm having a hard time selecting an answer, because many are helpful). However, I just wanted to comment on the definition of determinism as it's already very highly controversial topic when it's about nature so that people don't go there :-) Cheers! – The Quantum Physicist Sep 19 '17 at 15:44
  • Do any implementations of `malloc()`, `realloc()` and `free()` provide deterministic guarantees if you stay under a certain memory limit and follow certain rules? – Davislor Sep 19 '17 at 21:07
  • 1
    If you're defining deterministic execution as *following the same execution path* then practically no program which does I/O is going to be deterministic. – Russell Borogove Sep 19 '17 at 21:09
  • 9
    @PeterA.Schneider It is trivial to do non-deterministic things in almost all modern computers. One easy way -- note the least significant bit of the processor's instruction counter in a routine that waits for a disk read to complete. This is influenced by shear turbulence in the speed of the disk's rotation. You can do something similar with a network packet, which is influenced by microscopic zone temperature variations in quartz crystals that affect the skew between the network interface clock and the CPU clock. You can extract thermal noise from audio inputs.There are many other ways. – David Schwartz Sep 19 '17 at 21:40
  • @DavidSchwartz: You mean cycle / timestamp counter (like x86 [`rdtsc`](http://felixcloutier.com/x86/RDTSC.html)). It doesn't count instructions. "Instruction counter" is not a standard term, but it could mean either the PC aka IP register (instruction pointer) which depends only on ASLR; or that phrase could refer to a performance counter like x86's `inst_retired.any` (which is precise and deterministic). – Peter Cordes Sep 20 '17 at 05:27
  • 6
    @PeterA.Schneider: Most x86 CPUs these days (Intel since IvyBridge) have an [`rdrand`](http://felixcloutier.com/x86/RDRAND.html) instruction built-in, which you can execute from an ordinary user-space process. It gives true hardware randomness from [a thermal noise generator, conditioned with AES](https://en.wikipedia.org/wiki/RdRand) (unless the NSA weakened the design...). Of course, `rdtsc` is also non-deterministic as David points out, especially considering just a single process, but good point that sync between different clock domains gives some real non-determinism. – Peter Cordes Sep 20 '17 at 05:38
  • IMO due to existence of undefined behavior (and its trickiness) languages such as C and C++ should not be used to write safety critical applications - because it makes harder to write stable programs more than say in Java where UB doesn't exist. – Giorgi Moniava Sep 20 '17 at 08:10
  • @TheQuantumPhysicist: your typical PC is *almost* deterministic, and the fun is to understand what *almost* means. In many (but not all) cases we prefer to believe that it is deterministic (but we do know it is not!) – Basile Starynkevitch Sep 20 '17 at 12:23
  • @BasileStarynkevitch I have a comment up there that says that I agree with you. :-) – The Quantum Physicist Sep 20 '17 at 12:35
  • @PeterCordes On x86, it'd be `rdtsc`. An instruction counter would work just as well. Yes, the counter is deterministic, but as I explained, if you read the counter after something non-deterministic happens, the result of the read of the counter is non-deterministic. You can also usually extract thermal noise several ways, including looking at low order bits of the audio digitizer. – David Schwartz Sep 20 '17 at 16:34

12 Answers12

70

In the context of realtime systems, there is more to determinism than a repeatable "execution path". Another required property is that timing of key events is bounded. In hard realtime systems, an event that occurs outside its allowed time interval (either before the start of that interval, or after the end) represents a system failure.

In this context, usage of dynamic memory allocation can cause non-determinism, particularly if the program has a varying pattern of allocating, deallocating, and reallocating. The timing of allocations, deallocation, and reallocation can vary over time - and therefore making timings for the system as a whole unpredictable.

Peter
  • 35,646
  • 4
  • 32
  • 74
  • 29
    Mind you, unpredictable timings do not make a system non-realtime. if an allocation takes `rand()` milliseconds, and the time bound is more than `RAND_MAX`, the system is real-time. – MSalters Sep 19 '17 at 12:18
  • 4
    @MSalters - that's true. A realtime system requires the timings to be predictably bounded, not that each timing be predictable in advance. – Peter Sep 19 '17 at 22:34
  • 1
    Please: why do you call it "(non-) determinism" then? It's just an operation without a well defined worst case execution time. It only becomes "non-deterministic" if allocation is affected from e.g. other processes / parts of the application that interact with the "outside" (e.g. waiting for some human pressing a button). – Daniel Jour Sep 21 '17 at 00:41
  • If it's a true closed system, you could call it deterministic, but it'd still be *chaotic*, i.e. impossible to predict. That being said, I doubt it is a truly closed system, since that would be pretty useless. – John Wu Sep 21 '17 at 03:26
  • @DanielJour - the definition of a realtime system involves deterministic timing of events (e.g. it can be determined by analysing properties of the system that event B WILL occur between x and y milliseconds after event A). If the process of triggering or responding to events does not have a defined worst-case execution time, then the system cannot meet its realtime requirement. In a soft realtime system, that might be acceptable to a degree. In a hard realtime system, it is not. – Peter Sep 21 '17 at 09:51
  • @MSalters ...right...and real-time does not imply 'fast' either. – martin.dowie Apr 23 '20 at 14:42
  • The second part is confusing because it seems to imply that memory allocation is *inherently* non-deterministic (in the CS sense). It is not; as @MSalters said correctly in his answer, memory managers suitable for real-time systems do exist. – Pavel Kirienko Sep 21 '20 at 18:31
  • @PavelKirienko - The "second part" says nothing of the sort. – Peter Sep 22 '20 at 13:16
40

The comment, as stated, is incorrect.

Using a heap manager with non-deterministic behavior creates a program with non-deterministic behavior. But that is obvious.

Slightly less obvious is the existence of heap managers with deterministic behavior. Perhaps the most well-known example is the pool allocator. It has an array of N*M bytes, and an available[] mask of N bits. To allocate, it checks for the first available entry (bit test, O(N), deterministic upper bound). To deallocate, it sets the available bit (O(1)). malloc(X) will round up X to the next biggest value of M to choose the right pool.

This might not be very efficient, especially if your choices of N and M are too high. And if you choose too low, your program can fail. But the limits for N and M can be lower than for an equivalent program without dynamic memory allocation.

MSalters
  • 173,980
  • 10
  • 155
  • 350
  • cyclic buffer is a variation of this allocator, it can even be allocated using a single malloc at the begging of execution, then there are other mutations based on the context- if you know in advance you need N different buffer sizes then you can build an allocator that is more efficient. – Rsf Sep 19 '17 at 13:11
  • 1
    An alternative approach to using a bitmask for a pool collector is to use a linked list, which has O(1) allocation and deallocation. So long as code never tries to allocate more buffers of a certain size than exist in the pool, however, timing will be fully deterministic aside from caching issues. – supercat Sep 19 '17 at 16:13
  • 1
    The more general case is making the allocations up front, before deterministic behavior is required. Like the memory this pool allocator needs :) – Hans Passant Sep 20 '17 at 00:15
  • I am here on a mission to break a seemingly common misconception among embedded engineers that arbitrary-size memory allocation (as in `malloc()` rather than fixed-size blocks) is inherently non-time deterministic or may lead to unbounded fragmentation. As shown, for example, in "Timing-Predictable Memory Allocation In Hard Real-Time Systems" [Herter 2014], predictable and efficient algorithms exist, but they are rarely spoken of. I implemented one in ~500 lines of code here for a real-time embedded system I've been involved with: https://github.com/pavel-kirienko/o1heap – Pavel Kirienko Sep 21 '20 at 18:26
21

Nothing in the C11 standard or in n1570 says that malloc is deterministic (or is not); and neither some other documentation like malloc(3) on Linux. BTW, many malloc implementations are free software.

But malloc can (and does) fail, and its performance is not known (a typical call to malloc on my desktop would practically take less than a microsecond, but I could imagine weird situations where it might take much more, perhaps many milliseconds on a very loaded computer; read about thrashing). And my Linux desktop has ASLR (address space layout randomization) so runnning the same program twice gives different malloc-ed addresses (in the virtual address space of the process). BTW here is a deterministic (under specific assumptions that you need to elaborate) but practically useless malloc implementation.

determinism means that running a program twice will lead to the exact, same execution path

This is practically wrong in most embedded systems, because the physical environment is changing; for example, the software driving a rocket engine cannot expect that the thrust, or the drag, or the wind speed, etc... is exactly the same from one launch to the next one.

(so I am surprised that you believe or wish that real-time systems are deterministic; they never are! Perhaps you care about WCET, which is increasingly difficult to predict because of caches)

BTW some "real-time" or "embedded" systems are implementing their own malloc (or some variant of it). C++ programs can have their allocator-s, usable by standard containers. See also this and that, etc, etc.....

And high-level layers of embedded software (think of an autonomous automobile and its planning software) are certainly using heap allocation and perhaps even garbage collection techniques (some of which are "real-time"), but are generally not considered safety critical.

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
  • 6
    I think OP meant to say *running a program twice **with the exact same inputs*** should result in the same execution path, or same observable behaviour (or whatever other definition is preferred). – Toby Speight Sep 19 '17 at 14:28
  • But "observable behavior" is subjective (what about debugging `printf` with `%p` of result of `malloc`) and can lead to heated discussion – Basile Starynkevitch Sep 19 '17 at 14:38
  • A planner for an autonomous vehicle (or in fact any other piece of safety critical automotive software) will not use heap allocation or garbage collection. Dynamic memory allocation is prohibited by the [MISRA](https://en.wikipedia.org/wiki/Motor_Industry_Software_Reliability_Association) rules. – dasdingonesin Sep 21 '17 at 08:33
  • I used planning in the AI sense. All AI software for [planning](https://en.wikipedia.org/wiki/Automated_planning_and_scheduling) are using heap allocation (and most of them are using garbage collection and coded in very high-level AI languages, perhaps Lisp, Prolog, etc...). Of course, they are not safety-critical layers of such systems – Basile Starynkevitch Sep 21 '17 at 08:38
12

tl;dr: It's not that dynamic memory allocation is inherently non-deterministic (as you defined it in terms of identical execution paths); it's that it generally makes your program unpredictable. Specifically, you can't predict whether the allocator might fail in the face of an arbitrary sequence of inputs.

You could have a non-deterministic allocator. This is actually common outside of your real-time world, where operating systems use things like address layout randomization. Of course, that would make your program non-deterministic.

But that's not an interesting case, so let's assume a perfectly deterministic allocator: the same sequence of allocations and deallocations will always result in the same blocks in the same locations and those allocations and deallocations will always have a bounded running time.

Now your program can be deterministic: the same set of inputs will lead to exactly the same execution path.

The problem is that if you're allocating and freeing memory in response to inputs, you can't predict whether an allocation will ever fail (and failure is not an option).

First, your program could leak memory. So if it needs to run indefinitely, eventually an allocation will fail.

But even if you can prove there are no leaks, you would need to know that there's never an input sequence that could demand more memory than is available.

But even if you can prove that the program will never need more memory than is available, the allocator might, depending on the sequence of allocations and frees, fragment memory and thus eventually be unable to find a contiguous block to satisfy an allocation, even though there is enough free memory overall.

It's very difficult to prove that there's no sequence of inputs that will lead to pathological fragmentation.

You can design allocators to guarantee there won't be fragmentation (e.g., by allocating blocks of only one size), but that puts a substantial constraint on the caller and possibly increases the amount of memory required due to the waste. And the caller must still prove that there are no leaks and that there's a satiable upper-bound on total memory required regardless of the sequence of inputs. This burden is so high that it's actually simpler to design the system so that it doesn't use dynamic memory allocation.

Adrian McCarthy
  • 45,555
  • 16
  • 123
  • 175
  • The OP mentions space applications (high reliability) and microcontroller based applications. The real big problem for these is heap fragmentation and the unexpected allocation failures that can happen. The likelihood of this type of error occurring is high for the small memory spaces available on a microcontroller. To prevent this all memory should be statically allocated and the maximum stack usage carefully monitored. – uɐɪ Sep 20 '17 at 08:06
10

The deal with real-time systems is that program must strictly meet certain computation and memory restrictions regardless of the execution path taken (which may still vary considerably depending on input). So what does use of generic dynamic memory allocation (such as malloc/new) mean in this context? It means that developer at some point is not able to determine exact memory consumption and it would be impossible to tell whether resulting program will be able to meet the requirements, both for memory and for computation power.

user7860670
  • 35,849
  • 4
  • 58
  • 84
  • 4
    Well, uncompressing the same compressed file always leads to the same result, but suggesting to store the uncompressed result sort of misses the point of file compression ;). More seriously, route planners are a well-known example of entirely deterministic programs with a small input space (begin & end point) whose outcome matrix is far too large too store. – MSalters Sep 19 '17 at 12:21
  • 1
    This doesn't appear to answer the question that was asked; it answers some other question. As a reminder, the question was "does use of the heap make a program non-deterministic?" This doesn't answer that question. It might answer the question "is use of the heap problematic in real-time systems?", but that's a different question. – D.W. Sep 19 '17 at 16:20
8

Yes it is correct. For the kind of applications you mention, everything that can occur must be specified in detail. The program must handle the worst-case scenario according to specification and set aside exactly that much memory, no more, no less. The situation where "we don't know how many inputs we get" does not exist. The worst-case scenario is specified with fixed numbers.

Your program must be deterministic in a sense that it can handle everything up to the worst-case scenario.

The very purpose of the heap is to allow several unrelated applications to share RAM memory, such as in a PC, where the amount of programs/processes/threads running isn't deterministic. This scenario does not exist in a real-time system.

In addition, the heap is non-deterministic in its nature, as segments get added or removed over time.

More info here: https://electronics.stackexchange.com/a/171581/6102

Lundin
  • 195,001
  • 40
  • 254
  • 396
  • 2
    "deterministic in a sense that it can handle everything up to the worst-case scenario" - That's not what the word deterministic means. Not everything that is poor engineering is non-deterministic. – D.W. Sep 19 '17 at 16:22
  • 1
    @D.W. If you specify that you program should be able to handle up 100 things, then you design for that and expect deterministic behavior for all cases up to 100. If you go outside the specified limits, all bets are off and the result is indeterminate. This is actually what deterministic does mean. An alternative would be to not set an upper limit and heap allocate. The point where the program will go haywire can't be easily determined then. It depends on heap size, heap fragmentation and a lot of things. Similarly if you allow "any amount of input" instead of a deterministic maximum. – Lundin Sep 22 '17 at 12:02
6

Even if your heap allocator has repeatable behavior (the same sequence of allocation and free calls yield the same sequence of blocks, hence (hopefully) the same internal heap state), the state of the heap may vary drastically if the sequence of calls is changed, potentially leading to fragmentation that will cause memory allocation failures in an unpredictable way.

The reason heap allocation is frowned upon of downright forbidden in embedded systems, esp. mission critical systems such as aircraft or spacecraft guidance or life support systems is there is no way to test all possible variations in the sequence of malloc/free calls that can happen in response to intrinsically asynchronous events.

The solution is for each handler to have its one memory set aside for its purpose and it does not matter anymore (at least as far as memory use is concerned) in what order these handlers are invoked.

chqrlie
  • 131,814
  • 10
  • 121
  • 189
4

The problem with using heap in hard realtime software is heap allocations can fail. What do you when you run out of heap?

You are talking about space applications. You have pretty hard no-fail requirements. You must have no possibility of leaking memory so there is not enough for at least the safe mode code to run. You must not fall over. You must not throw exceptions that have no catch block. You probably don't have an OS with protected memory so one crashing application can in theory take out everything.

You probably don't want to use heap at all. The benefits don't outweigh the whole-program costs.

Non-determinsitic normally means something else but in this case the best read is they want the entire program behavior completely predictable.

Joshua
  • 40,822
  • 8
  • 72
  • 132
2

Short answer

There are some effects on the data values or their statistical uncertainty distributions of, e.g, a first or second level trigger scintillator device that can derive from the non-reproducible quantity of time that you may have to wait for malloc/free.

The worst aspect is that they are not related to the physical phenomenon either with the hardware but somehow with the state of the memory (and its history).

Your goal, in that case, is to reconstruct the original sequence of events from the data affected by those errors. The reconstructed/guessed sequence will be affected by errors too. Not always this iteration will convergence on a stable solution; it is not said it will be the correct one; your data is not any more independent... You risk a logical short-circuit...

Longer answer

You stated "I wasn't able to verify the correctness of this statement when people tell me that".
I will try to give you a purely hypothetical situation/ case study.

Let's we imagine you deal with a CCD or with some 1st and 2nd level scintillator triggers on a system that have to economize resources (you're in space).
The acquisition rate will be set so that the background will be at x% of the MAXBINCOUNT.

  • There's a burst, you have a spike in the counts and an overflow in the bin counter.
    I want it all: you switch to the max acquisition rate and you finish your buffer.
    You go to free/allocate more memory meanwhile you finish the extra buffer.
    What will you do?

    1. You will keep the counteractive risking the overflow (the second level will try to count properly the timing of the data-packages) but in this case, you will go to underestimate the counts for that period?
    2. you will stop the counter introducing a hole in the time series?

    Note that:

    • Waiting for allocation you will lose the transient (or at least its beginning).
    • Whatever you do it depends on the state of your memory and it is not reproducible.

  • Now instead the signal is variable around the maxbincount at the maximum acquisition rate allowed from your hardware, and the event is longer than usual.
    You finish the space and ask for more... meanwhile, you incur in the same problem above.
    Overflow and systematic peaks counts underestimation or holes in the time series?

Let we move a second level (it can be on the 1st level trigger too).

From your hardware, you receive more data than you can stock or transmit.
You have to cluster the data in time or space (2x2, 4x4, ... 16x16 ... 256x256... pixel scaling...).

The uncertainty from the previous problem may affect the error distribution.
There are CCD setting for which you have the pixels of the border with counts close to the maxbincount (it depends from "where" you want to see better).
Now you can have a shower on your CCD or a single big spot with the same total number of counts but with a different statistical uncertainty (the part that is introduced by the waiting time)...

So for example where you are expecting a Lorentzian profile you can obtain its convolution with a Gaussian one (a Voigt), or if the second it's really dominant with a dirty Gaussian...

Farzad Karimi
  • 770
  • 1
  • 12
  • 31
Hastur
  • 2,470
  • 27
  • 36
2

Introduce Integrity RTOS from GHS:

https://www.ghs.com/products/rtos/integrity.html

and LynxOS:

http://www.lynx.com/products/real-time-operating-systems/lynxos-178-rtos-for-do-178b-software-certification/

LynxOS and Integrity RTOS are among the software used in space applications, missiles, aircraft etc as many others are not approved or certified by authorities (eg, FAA).

https://www.ghs.com/news/230210r.html

To meet the stringent criteria of space applications, Integrity RTOS actually provide formal verification, ie, mathematically proven logic, that their software behave as according to specification.

Among these criteria, to quote from here:

https://en.wikipedia.org/wiki/Integrity_(operating_system)

and here:

Green Hills Integrity Dynamic memory allocation

is this:

enter image description here

I am not a specialist in formal methods, but perhaps one of the requirements for this verification is to remove the uncertainties in the timing required for memory allocation. In RTOS, all event is precisely planned milliseconds away from each other. And dynamic memory allocation always have a problem with timing required.

Mathematically you really need to prove everything worked from most fundamental assumptions about timing and amount of memory.

And if you think of the alternatives to heap memory: static memory. The address is fixed, the size allocated is fixed. The position in memory is fixed. So it is very easy to reason about memory sufficiency, reliability, availability etc.

Peter Teoh
  • 6,337
  • 4
  • 42
  • 58
  • 1
    Technically, as a closed system, it is deterministic, but also chaotic, ie. impossible to predict. – John Wu Sep 21 '17 at 03:23
0

malloc, free, new, delete

There are various techniques to mitigate issues with dynamic memory allocation. For instance, you can allocate all objects using the 'in-place new' operator, or allocate them all at once during startup using the heap. However, if dynamic memory allocation is unavoidable, there are specialized memory allocator implementations that can be employed.

Real Time Heap Allocator

There are various heap allocation algorithms used across platforms, such as Dlmalloc, Phkmalloc, ptmalloc, jemalloc, Google Chrome's PartitionAlloc, and the glibc heap allocator. While each has its benefits, they aren't tailored for hard real-time environments prioritizing speed, determinism, minimal fragmentation, and memory safety.

The main requirements for Real Time Heap Allocator are:

Predictable Execution Time: The worst-case execution time for the 'malloc, free' and 'new delete C++' functions must be deterministic and independent of application data.

Memory Pool Preservation: The algorithm must strive to minimize the likelihood of exhausting the memory pool. This can be achieved by reducing fragmentation and minimizing memory waste.

Fragmentation Management: The algorithms should effectively manage and reduce external fragmentation, which can limit the amount of available free memory.

Defined Behavior: The allocator must aim to eliminate any undefined behavior to ensure consistency and reliability in its operations.

Functional Safety; The allocator must adhere to the principles of functional safety. It should consistently perform its intended function during normal and abnormal conditions. Its design must consider and mitigate possible failure modes, errors, and faults.

When we talk about 'functional safety'in RTSHA, we are not referring to 'security'. "Functional safety" refers to the aspect of a system's design that ensures it operates correctly in response to its inputs and failures, minimizing risk of physical harm, while "security" refers to the measures taken to protect a system from unauthorized access, disruption, or damage. *

Error Detection and Handling: The allocator should have mechanisms to detect and handle memory allocation errors or failures. This can include robust error reporting, and fallback or recovery strategies in case of allocation failures.

Support for Different Algorithms: The allocator should be flexible enough to support different memory allocation algorithms, allowing it to be adapted to the specific needs of different applications.

Configurability: The allocator should be configurable to suit the requirements of specific platforms and applications. This includes adjusting parameters like the size of the memory pool, the size of allocation blocks, and the allocation strategy.

Efficiency: The allocator should be efficient, in terms of both time and space. It should aim for minimal overhead and quick allocation and deallocation times.

Readability and Maintainability: The code for the allocator should be clear, well-documented, and easy to maintain. This includes adhering to good coding practices, such as using meaningful variable names and including comments that explain the code.

Compatibility: The allocator should be compatible with the system it is designed for and work well with other components of the system.

The Real Time Safety Heap Allocator (RTSHA) I authored, available on GitHub, is an ultra-fast memory management system designed to meet those requirements.

There are several different algorithms that can be used for heap allocation supported by RTSHA:

Small Fix Memory Pages

This algorithm is an approach to memory management that is often used in specific situations where objects of a certain size are frequently allocated and deallocated. By using of uses 'Fixed chunk size' algorithm greatly simplies the memory allocation process and reduce fragmentation.

The memory is divided into pages of chunks(blocks) of a fixed size (32, 64, 128, 256 and 512 bytes). When an allocation request comes in, it can simply be given one of these blocks. This means that the allocator doesn't have to search through the heap to find a block of the right size, which can improve performance. The free blocks memory is used as 'free list' storage. The list is implemented using a standard linked list. However, by enabling the precompiler option USE_STL_LIST, the STL version of the forward list can also be utilized. There isn't a significant performance difference between the two implementations.

Deallocations are also straightforward, as the block is added back to the list of available chunks. There's no need to merge adjacent free blocks, as there is with some other allocation strategies, which can also improve performance.

However, fixed chunk size allocation is not a good fit for all scenarios. It works best when the majority of allocations are of the same size, or a small number of different sizes. If allocations requests are of widely varying sizes, then this approach can lead to a lot of wasted memory, as small allocations take up an entire chunk, and large allocations require multiple chunks.

Small Fix Memory Page is also used internaly by "Power Two Memory Page" and "Big Memory Page" algorithms.

Power Two Memory Pages

This algorithm is a more intricate system that exclusively allows blocks of sizes that are powers of two. This design makes merging free blocks back together easier and significantly reduces fragmentation. The core of this algorithm is based on an array of free lists. Each list corresponds to one group of power-of-two sizes. For instance, there's a dedicated list for 64-byte free blocks, another for 128-byte blocks, and so on. This structured approach ensures that blocks of a specific size are readily available, optimizing memory management and access. This method ensures efficient block allocation and deallocation operations, making the most of the power-of-two size constraint. Utilizing the combination of power-of-two block sizes with an array of free lists and a binary search mechanism, this algorithm strikes a balance between memory efficiency and operational speed. This is a fairly efficient method of allocating memory, particularly useful for systems where memory fragmentation is an important concern. The algorithm divides memory into partitions to try to minimize fragmentation and the 'Best Fit' algorithm searches the page to find the smallest block that is large enough to satisfy the allocation. Furthermore, this system is resistant to breakdowns due to its algorithmic approach to allocating and deallocating memory. The coalescing operation helps ensure that large contiguous blocks of memory can be reformed after they are freed, reducing the likelihood of fragmentation over time. Coalescing relies on having free blocks of the same size available, which is not always the case, and so this system does not completely eliminate fragmentation but rather aims to minimize it. Measured Performance on Cortex-M7

Based on the results obtained from the system's profiling, here are the performance metrics in terms of CPU cycles for the memory operations:

Small Fix Page:

rtsha_malloc: 204 cycles rtsha_free: 193 cycles

This represents the time taken for memory allocation and deallocation for smaller fixed-size pages, specifically designed for handling memory chunks less than 512 bytes.

Power2 Page:

rtsha_malloc: 873 cycles rtsha_free: 636 cycles

Boris Radonic
  • 13
  • 3
  • 1
    did you use chatgpt or any similar AI at all to write any part of this answer? – starball Aug 25 '23 at 16:43
  • I am author of Real Time Safety Heap Allocator (RTSHA). https://github.com/borisRadonic/RTSHA I occasionally use ChatGPT to refine and optimize my sentences since I'm not a native English speaker. – Boris Radonic Aug 25 '23 at 16:47
-3

There is a trade-off always. It's the program's running environment and the tasks it performs that should be the basis to decide whether HEAP should be used or not.

Heap object is efficient when you want to share the data between multiple function calls. You just need to pass the pointer since heap is globally accessible. There are disadvantages as well. Some function might free up this memory but still some references may exist at other places as well.

If the heap memory is not freed after it's work is done and the program keeps on allocating more memory, at some point HEAP will run out of memory and affects the deterministic character of the program.

Naresh
  • 13
  • 1
  • 1
    "You just need to pass the pointer since heap is globally accessible." And this is different from `.data` and `.bss` how...? – Lundin Sep 19 '17 at 11:09
  • 5
    One can create global stack variables... where's the problem in that? They can be passed between functions, too. – The Quantum Physicist Sep 19 '17 at 11:12
  • 2
    This doesn't appear to answer the question that was asked; it answers some other question. As a reminder, the question was "does use of the heap make a program non-deterministic?" This doesn't answer that question. It might answer the question "is use of the heap a good idea in real-time systems?", but that's a different question. The last phrase starts to head in that direction, but you don't say *how* it affects the deterministic character of the program, or why, and don't answer the question. – D.W. Sep 19 '17 at 16:23