Practical Memory Pool Based Allocators For Modern C++
0:08 Introduction: Misha Shalem introduces the topic of memory pool based allocators in modern C++, particularly in the context of safety-critical real-time systems like ROS 2 for autonomous driving.
1:15 Challenges of Real-Time Memory Allocation: In safety-critical environments, memory allocation must be deterministic, certifiable, avoid fragmentation, and not rely on non-deterministic kernel calls.
2:17 Autosar C++ Guidelines: Autosar guidelines are highlighted as a relevant standard for memory management in such systems, emphasizing deterministic behavior and avoiding memory issues.
3:11 Dynamic Memory Allocation Restriction: The guidelines permit dynamic memory allocation only during the initialization phase, not during operational mode.
3:36 Memory Pool Benefits: Memory pools with fixed block sizes are presented as a solution due to their deterministic behavior, constant-time allocation/deallocation, and ease of implementation and understanding.
4:54 The C++ Allocator Problem: Standard C++ containers like std::map and std::list accept custom allocators but do not directly use them for their internal node allocations, making it difficult to determine block sizes at compile time.
7:16 The Rebind Solution: The presentation explains how the rebind construct in allocators can be leveraged to allocate memory for internal node types, even though they are hidden from the user.
8:38 Three-Step Approach: The proposed solution involves creating a memory pool, an allocator that utilizes the memory pool, and a mechanism to generate bucket definitions (block size and count) based on the allocator's behavior.
9:11 Memory Pool Implementation: A basic memory pool implementation is shown, using a ledger to track allocated blocks within each bucket.
14:22 Pool Configuration: The concept of defining memory pools through bucket_descriptors type traits is introduced, allowing for multiple pools with different bucket configurations.
18:44 Choosing the Right Bucket: A naive "first-fit" approach for bucket selection is discussed and shown to be inadequate for containers like std::unordered_map that may allocate multiple elements of different sizes at once.
22:41 Addressing Fragmentation: The presentation acknowledges that allocating variable numbers of blocks can introduce fragmentation within a bucket. However, it suggests that this is manageable with careful memory pool separation and understanding of allocation patterns, especially in embedded systems where container sizes are often fixed.
30:35 Allocator Implementation: A custom allocator, static_pool_allocator, is demonstrated. It is bound to a specific memory pool ID at compile time to prevent accidental migration of data between pools.
31:34 Transparent Fallback: The allocator uses an upstream resource (e.g., the heap) for allocation until the memory pool is fully defined, allowing for development and testing before switching to the memory pool in the operational phase.
36:58 Collecting Type Sizes: The importance of collecting type sizes for all allocations is emphasized. Direct printing is deemed insufficient as it lacks context (call graph) and can be difficult to ensure complete coverage.
38:57 Instrumentation: A dummy function, type_track, is introduced for instrumentation. It's called during allocation, effectively recording the type and size information in the compiled code.
40:19 Allocation Analyzer (LLVM Pass): An LLVM pass is developed to analyze the compiled bitcode, extract type_track calls, build a call graph for each allocation, and generate memory pool definitions.
47:01 Call Graph Caveats: Limitations of call graph construction due to virtual calls, function pointers, and inline assembly are discussed. Combining runtime analysis with the LLVM pass is suggested as a mitigation strategy.
48:30 Generating Memory Pool Definitions: The LLVM pass generates a header file containing bucket_descriptors specializations, effectively defining the memory pool structure based on the analyzed code.
49:54 Conclusion: The presentation concludes by summarizing the approach and highlighting its benefits as a certifiable solution for deterministic memory management in C++, particularly for safety-critical real-time systems.
51:03 Q&A: The Q&A session clarifies implementation details like the use of malloc (historical reasons, could be replaced with new), addresses considerations for physically contiguous memory (kernel-level allocators), explains LLVM bitcode, and discusses handling exceptions in critical systems.