1.. _module-pw_allocator-design: 2 3================ 4Design & roadmap 5================ 6.. pigweed-module-subpage:: 7 :name: pw_allocator 8 9----------------------- 10Design of pw::Allocator 11----------------------- 12Traditionally, most embedded firmware have laid out their systems’ memory usage 13statically, with every component’s buffers and resources set at compile time. As 14systems grow larger and more complex, dynamic allocation provides increasing 15opportunities to simplify code and improve memory usage by enabling sharing and 16eliminating large reservations. 17 18As a result, ``pw_allocator`` seeks to make dynamic allocation possible without 19sacrificing too much of the control over memory usage that embedded developers 20are accustomed to and need. The fundamental design goals of ``pw_allocator`` are 21for allocators to be: 22 23- Familiar: The interface and its usage should resemble that of C++17's 24 `std::pmr::polymorphic_allocator`_ type. 25- Flexible: A diverse set of allocation strategies should be implementable 26 using allocators. 27- Composable: Allocators should be able to combine and use other allocators. 28- Extensible: Downstream projects should be able to provide their own allocator 29 implementations, and easily integrate them with Pigweed's. 30- Cost-effective: Projects should be able to include only the allocator 31 behaviors they desire. 32- Observable: Allocators should provide tools and data to reveal how memory is 33 being used. 34- Correcting: Allocators should include features to help uncover 35 `memory defects`_ including heap corruption, leaks, use-after-frees, etc. 36 37.. _module-pw_allocator-design-differences-with-polymorphic-allocators: 38 39Differences with C++ polymorphic allocators 40=========================================== 41C++17 introduced the ``<memory_resource>`` header with support for polymorphic 42memory resources (PMR), i.e. allocators. This library defines many allocator 43interfaces similar to those in ``pw_allocator``. 44 45Pigweed has decided to keep ``pw_allocator`` distinct from PMR primarily because 46the latter's interface requires the use of C++ language features prohibited by 47Pigweed. In PMR, allocators are expected to throw an exception in the case of 48failure, and equality comparisons require runtime type identification (RTTI). 49 50Even so, ``pw_allocator`` has taken inspiration from the design of PMR, 51incorporating many of its ideas. :ref:`module-pw_allocator-api-allocator` in 52particular is similar to `std::pmr::memory_resource`_. 53 54This similarity is most evident in the PMR adapter class, 55:ref:`module-pw_allocator-api-pmr_allocator`. This adapter allows any 56:ref:`module-pw_allocator-api-allocator` to be used as a 57`std::pmr::polymorphic_allocator`_ with any standard library that 58`can use an allocator`_. Refer to the guides on how to 59:ref:`module-pw_allocator-use-standard-library-containers`. 60 61.. _module-pw_allocator-design-forwarding: 62 63Forwarding allocator concept 64============================ 65In addition to concrete allocator implementations, the design of 66``pw_allocator`` also encourages the use of "forwarding" allocators. These are 67implementations of the :ref:`module-pw_allocator-api-allocator` interface that 68don't allocate memory directly and instead rely on other allocators while 69providing some additional behavior. 70 71For example, the :ref:`module-pw_allocator-api-allocator` records various 72metrics such as the peak number of bytes allocated and the number of failed 73allocation requests. It wraps another allocator which is used to actually 74perform dynamic allocation. It implements the allocator API, and so it can be 75passed into any routines that use dependency injection by taking a generic 76:ref:`module-pw_allocator-api-allocator` parameter. 77 78These "forwarding" allocators are not completely free. At a miniumum, they 79represent an extra virtual indirection, and an extra function call, albeit one 80that can often be inlined. Additional behavior-specific code or state adds to 81their cost in terms of code size and performance. Even so, these "forwarding" 82allocators can provide savings relative to a "`golden hammer`_"-style allocator 83that combined all of their features and more. By decomposing allocators into 84orthogonal behaviors, implementers can choose to pay for only those that they 85want. 86 87----------------------------- 88Design of allocator utilities 89----------------------------- 90In addtion to providing allocator implementations themselves, ``pw_allocator`` 91includes some foundational classes that can be used to implement allocators. 92 93.. _module-pw_allocator-design-block: 94 95pw::allocator::Block 96==================== 97Several allocators make use of allocation metadata stored inline with the 98allocations themselves. Often referred to as a "header", this metadata 99immediately precedes the pointer to usable space returned by the allocator. This 100header allows allocations to be variably sized, and converts allocation into a 101`bin packing problem`_. An allocator that uses headers has a miniumum alignment 102matching that of the header type itself. 103 104For ``pw_allocator``, the most common way to store this header is as a 105:ref:`module-pw_allocator-api-block`. This class is used to construct a 106doubly-linked list of subsequences of the allocator's memory region. It was 107designed with the following features: 108 109- **Templated offset types**: Rather than use pointers to the next and previous 110 blocks, ``Block`` uses offsets of a templated unsigned integral type. This 111 saves a few bits that can be used for other purposes, since the blocks are 112 always aligned to the block header. It also gives callers the ability to 113 reduce the size of the headers if the allocator's memory region is 114 sufficently small, e.g. a type of ``uint16_t`` could be used if the region 115 could hold no more than 65536 block headers. 116- **Splitting and merging**: This class centralizes the logic for splitting 117 memory regions into smaller pieces. Usable sub-blocks can either be split from 118 the beginning or end of a block. Additionally, blocks from either end can be 119 split at specified alignment boundaries. This class also provides the logic 120 for merging blocks back together. Together, these methods provide the 121 invariant that a free block is only ever adjacent to blocks in use. 122- **Validation and poisoning**: On every deallocation, blocks validate their 123 metadata against their neighbors. A block can fail to be validated if it or 124 its neighbors have had their headers overwritten. In this case, it's unsafe to 125 continue to use this memory and the block code will assert in order make you 126 aware of the problem. Additionally, blocks can "paint" their memory with a 127 known poison pattern that's checked whenever the memory is next allocated. If 128 the check fails, then some code has written to unallocated memory. Again, the 129 block code will assert to alert you of a "use-after-free" condition. 130 131.. tip:: 132 In the case of memory corruption, the validation routines themsleves may 133 crash while attempting to inspect block headers. These crashes are not 134 exploitable from a security perspective, but lack the diagnostic information 135 from the usual ``PW_CHECK`` macro. Examining a stack trace may be helpful in 136 determining why validation failed. 137 138.. _module-pw_allocator-design-metrics: 139 140Allocator metrics 141================= 142A common desire for a project using dynamic memory is to clearly understand how 143much memory is being allocated. However, each tracked metric adds code size, 144memory overhead, and a per-call performance cost. As a result, ``pw_allocator`` 145is design to allow allocator implementers to select just the metrics they're 146interested in. 147 148In particular, the :ref:`module-pw_allocator-api-metrics_adapter` uses 149per-metric type traits generated by ``PW_ALLOCATOR_METRICS_DECLARE`` to 150conditionally include the code to update the metrics that are included in its 151``MetricsType`` template parameter type. A suitable ``MetricType`` struct can be 152created using the ``PW_ALLOCATOR_METRICS_ENABLE`` macro, which will only create 153fields for the enabled metrics. 154 155Using these macros prevents unwanted metrics from increasing either the code 156size or object size of the metrics adapter, and by extension, 157:ref:`module-pw_allocator-api-tracking_allocator`. 158 159------- 160Roadmap 161------- 162While the :ref:`module-pw_allocator-api-allocator` interface is almost stable, 163there are some outstanding features the Pigweed team would like to add to 164``pw_allocator``: 165 166- **Asynchronous allocators**: Determine whether these should be provided, and 167 if so, add them. 168- **Additional smart pointers**: Determine if pointers like ``std::shared_ptr``, 169 etc., are needed, and if so, add them. 170- **Dynamic containers**: Provide the concept of allocator equality without 171 using RTTI or ``typeid``. This would allow dynamic containers with their own 172 allocators. 173- **Default allocators**: Integrate ``pw_allocator`` into the monolithic 174 ``pw_system`` as a starting point for projects. 175 176Found a bug? Got a feature request? Please create a new issue in our `tracker`_! 177 178Want to discuss allocators in real-time with the Pigweed team? Head over to our 179`Discord`_! 180 181.. _memory defects: https://en.wikipedia.org/wiki/Memory_corruption 182.. _golden hammer: https://en.wikipedia.org/wiki/Law_of_the_instrument#Computer_programming 183.. _bin packing problem: https://en.wikipedia.org/wiki/Bin_packing_problem 184.. _std::pmr::memory_resource: https://en.cppreference.com/w/cpp/memory/memory_resource 185.. _std::pmr::polymorphic_allocator: https://en.cppreference.com/w/cpp/memory/polymorphic_allocator 186.. _can use an allocator: https://en.cppreference.com/w/cpp/memory/uses_allocator 187.. _tracker: https://pwbug.dev 188.. _Discord: https://discord.gg/M9NSeTA 189