Addressing dynamic memory allocation in safe and time predictable systems

Dynamic memory allocation is a pivotal feature of modern software systems but has mostly been used in general-purpose systems. Due to the limited time predictability of dynamic memory allocators (DynMAs), their use in real-time systems is often discouraged. Moreover, many safety standards and software guidelines such as ISO 26262 suggest to avoid the usage of such a feature in a safety domain. The first part of this thesis focuses on safety-critical systems, which require software implemented under stringent rules and guidelines. As system designers are transitioning to the usage of pre-existing software architectural elements to reduce time-to-market and costs, they face challenges in safety-critical applications. Pre-existing software may have been implemented without following any safety and/or quality standard, and its documentation may be incomplete or unclear. The safety qualification of such software according to the functional safety standard ISO 26262 may hence be very time consuming and expensive if not approached in a structured way. To address this, the thesis introduces a structured methodology to achieve software hazardous behavior analysis. This approach is the starting point to identify criticalities or abnormal conditions in pre-existing software, which can then be mitigated with adequate safety measures. The proposed approach is applied to DynMA in the Linux kernel, driving the generation of its safety requirements to enable its integration into safety-critical applications. The second part of this thesis focuses on real-time systems, which require that the response time of each request is bounded and sufficiently tight. Although numerous general-purpose DynMAs have been developed over the years, only a few of them have been designed with the specific needs of real-time systems in mind. Furthermore, the most notable one dates back to almost 20 years ago. By analyzing and comparing modern allocators, the thesis describes the modifications applied to the Mimalloc general-purpose allocator to turn it into RT-Mimalloc, a real-time version designed to offer more predictable allocation times. Then, we present a real-time analysis of RT-Mimalloc, establishing bounds on both allocation and deallocation times. The evaluation of RT-Mimalloc is conducted using both modern benchmarks for memory allocation and synthetic workloads designed to test the allocator’s worst-case performance in real-time scenarios. The results demonstrate that RT-Mimalloc significantly improves the longest observed allocation times compared to previous real-time DynMAs, while maintaining the high average-case performance typical of modern general-purpose allocators. Finally, the same benchmarks have been used to compare empirical measurements with the analysis results and validate the allocation and deallocation bounds obtained from the real-time analysis of RT-Mimalloc.