Tracealyzing the FreeRTOS Kernel
November 19, 2021
Story
It is well known that when using languages such as C or C++ on embedded systems, great care must be taken when dealing with memory for several reasons. On one hand, because memory availability is often limited in embedded systems; on the other hand, because these systems often have a very long runtime, so memory fragmentation can lead to problems in the long run.
In the context of my master thesis ‘Bucket of Ignorance’, I wanted to test an improvement of the timer management in FreeRTOS. To maintain deterministic timing behaviors, Real-Time Operating Systems (RTOSes) require not only a task scheduler but also a timing mechanism for the periodicity of recurrent tasks. Most existing open-source RTOSes implement either a tree-based or a list-based mechanism to track which task is ready to release on-the-fly. Although tree-based mechanisms are known to be efficient in time complexity for searching operations, the additional effort spent processing removals and insertions is not negligible, which may countervail the advantage compared to list-based timer managers even with small task sets.
But both mechanisms share one weakness: They insert new elements directly at the correct position even if the value to be inserted is significantly higher than the first half of existing elements.
The central idea of ‘Bucket of Ignorance’ therefore is as follows: If the element to be inserted is higher than existing values in the used list or tree, the new element will be appended to a second, unsorted list. The sorted list or tree will become empty over time. When this happens, the unsorted list will be sorted using a merge-sort algorithm and the first half of the sorted elements will be moved to the sorted list / tree.
For full details about the mechanism refer to the paper (https://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/ebrrechttimer.pdf).
The improvement had been tested theoretically and proven to be more efficient in a simulator and must now be implemented in a real system. After the implementation on a system with FreeRTOS, (https://github.com/marcelebbrecht/rbas-node-freertos) tasks should be created and terminated dynamically during operation.
To implement the ‘Bucket of Ignorance’ timer mechanism, I had to make numerous changes to the FreeRTOS kernel. Unfortunately, instabilities occurred again and again during test runs. While the IDE I used, MCUXpresso, offered extensive debugging possibilities, the reason for the instabilities could not be found. However, the behavior of the system (errors occurred sporadically and especially when working close to the memory limit of the used platform ‘NXP LPC54018 IoT Module’) suggested problems in the memory management of the kernel and the individual processes. However, such issues could not be investigated with the IDE.
Looking for a suitable tool that allows tracing memory operations at runtime under FreeRTOS, I came across Tracealyzer relatively quickly. The necessary functions were integrated in FreeRTOS within a few minutes, the installation of the toolchain and the connection via J-Link in streaming mode worked immediately. By tracing memory allocation and memory sharing of the individual tasks and specific kernel functions using streaming mode, the error causes could be identified and eliminated.
Interestingly, Tracealyzer not only helped me find and fix errors in my own code, but also in already existing code parts. While this would have been possible without the use of Tracealyzer, it would have been considerably more time-consuming.
Marcel Ebbrecht, M.Sc Computer Science, TU Dortmund, Germany
