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.. _module-pw_allocator-design-blocks: 88 89Blocks of memory 90================ 91Several allocators make use of allocation metadata stored inline with the 92allocations themselves. Often referred to as a "header", this metadata 93immediately precedes the pointer to usable space returned by the allocator. This 94header allows allocations to be variably sized, and converts allocation into a 95`bin packing problem`_. An allocator that uses headers has a miniumum alignment 96matching that of the header type itself. 97 98For ``pw_allocator``, the most common way to store this header is as a 99:ref:`module-pw_allocator-api-block`. Specific block implementations are created 100by providing a concrete representation and implementing the required methods for 101one or more of the block mix-ins. Each block mix-in provides a specific set of 102features, allowing block implementers to include only what they need. Features 103provided by these block mix-ins include: 104 105- A :ref:`module-pw_allocator-api-basic_block` can retrieve the memory that 106 makes up its usable space and its size. 107- A :ref:`module-pw_allocator-api-contiguous_block` knows the blocks that are 108 adjacent to it in memory. It can merge with neighboring blocks and split 109 itself into smaller sub-blocks. 110- An :ref:`module-pw_allocator-api-allocatable_block` knows when it is free or 111 in-use. It can allocate new blocks from either the beginning or end of its 112 usable space when free. When in-use, it can be freed and merged with 113 neighboring blocks that are free. This ensures that free blocks are only ever 114 adjacent to blocks in use, and vice versa. 115- An :ref:`module-pw_allocator-api-alignable_block` can additionally allocate 116 blocks from either end at specified alignment boundaries. 117- A :ref:`module-pw_allocator-api-block_with_layout` can retrieve the layout 118 used to allocate it, even if the block itself is larger due to alignment or 119 padding. 120- The :ref:`module-pw_allocator-api-iterable_block` type provides iterators 121 and ranges that can be used to iterate over a sequence of blocks. 122- A :ref:`module-pw_allocator-api-poisonable_block` can fill its usable space 123 with a pattern when freed. This pattern can be checked on a subsequent 124 allocation to detect if the memory was illegally modified while free. 125 126You can use these mix-ins to implement your own block type, or use one of the 127implementations provided by Pigweed. Each of provided block types implements 128some or all of the mix-ins: 129 130.. list-table:: 131 :header-rows: 1 132 133 * - Mix-in 134 - BuddyBlock 135 - :ref:`module-pw_allocator-api-tiny_block` 136 - :ref:`module-pw_allocator-api-small_block` 137 - :ref:`module-pw_allocator-api-small_alignable_block` 138 - :ref:`module-pw_allocator-api-detailed_block` 139 * - :ref:`module-pw_allocator-api-basic_block` 140 - ✓ 141 - ✓ 142 - ✓ 143 - ✓ 144 - ✓ 145 * - :ref:`module-pw_allocator-api-contiguous_block` 146 - 147 - ✓ 148 - ✓ 149 - ✓ 150 - ✓ 151 * - :ref:`module-pw_allocator-api-iterable_block` 152 - 153 - ✓ 154 - ✓ 155 - ✓ 156 - ✓ 157 * - :ref:`module-pw_allocator-api-allocatable_block` 158 - 159 - ✓ 160 - ✓ 161 - ✓ 162 - ✓ 163 * - :ref:`module-pw_allocator-api-alignable_block` 164 - 165 - 166 - 167 - ✓ 168 - ✓ 169 * - :ref:`module-pw_allocator-api-poisonable_block` 170 - 171 - 172 - 173 - 174 - ✓ 175 * - :ref:`module-pw_allocator-api-block_with_layout` 176 - 177 - 178 - 179 - 180 - ✓ 181 182.. note:: 183 ``BuddyBlock`` is a specialized implementation used by 184 :ref:`module-pw_allocator-api-buddy_allocator`. It is not general enough to 185 be used with a generic :ref:`module-pw_allocator-api-block_allocator`. 186 187In addition to poisoning, blocks validate their metadata against their neighbors 188on each allocation and deallocation. A block can fail to be validated if it or 189its neighbors have had their headers overwritten. In this case, it's unsafe to 190continue to use this memory and the block code will assert in order make you 191aware of the problem. 192 193.. tip:: 194 In the case of memory corruption, the validation routines themsleves may 195 crash while attempting to inspect block headers. These crashes are not 196 exploitable from a security perspective, but lack the diagnostic information 197 from the usual ``PW_CHECK`` macro. Examining a stack trace may be helpful in 198 determining why validation failed. 199 200.. _module-pw_allocator-design-buckets: 201 202Buckets of blocks 203================= 204The most important role of a :ref:`module-pw_allocator-api-block_allocator` is 205to choose the right block to satisfy an allocation request. Different block 206allocators use different strategies to accomplish this, and thus need different 207data structures to organize blocks in order to be able to choose them 208efficiently. 209 210For example, a block allocator that uses a "best-fit" strategy needs to be able 211to efficiently search free blocks by usable size in order to find the smallest 212candidate that could satisfy the request. 213 214The :ref:`module-pw_allocator-api-basic_block` mix-in requires blocks to specify 215both a ``MinInnerSize`` and ``DefaultAlignment``. Together these ensure that the 216usable space of free blocks can be treated as intrusive items for containers. 217The bucket classes that derive from :ref:`module-pw_allocator-api-bucket_base` 218provide such containers to store and retrieve free blocks with different 219performance and code size characteristics. 220 221.. _module-pw_allocator-design-metrics: 222 223Buckets of blocks 224================= 225The most important role of a :ref:`module-pw_allocator-api-block_allocator` is 226to choose the right block to satisfy an allocation request. Different block 227allocators use different strategies to accomplish this, and thus need different 228data structures to organize blocks in order to be able to choose them 229efficiently. 230 231For example, a block allocator that uses a "best-fit" strategy needs to be able 232to efficiently search free blocks by usable size in order to find the smallest 233candidate that could satisfy the request. 234 235The :ref:`module-pw_allocator-api-basic_block` mix-in requires blocks to specify 236both a ``MinInnerSize`` and ``DefaultAlignment``. Together these ensure that the 237usable space of free blocks can be treated as intrusive items for containers. 238The :ref:`module-pw_allocator-api-bucket` provide such containers to store and 239retrieve free blocks with different performance and code size characteristics. 240 241Allocator metrics 242================= 243A common desire for a project using dynamic memory is to clearly understand how 244much memory is being allocated. However, each tracked metric adds code size, 245memory overhead, and a per-call performance cost. As a result, ``pw_allocator`` 246is design to allow allocator implementers to select just the metrics they're 247interested in. 248 249In particular, the :ref:`module-pw_allocator-api-metrics_adapter` uses 250per-metric type traits generated by ``PW_ALLOCATOR_METRICS_DECLARE`` to 251conditionally include the code to update the metrics that are included in its 252``MetricsType`` template parameter type. A suitable ``MetricType`` struct can be 253created using the ``PW_ALLOCATOR_METRICS_ENABLE`` macro, which will only create 254fields for the enabled metrics. 255 256Using these macros prevents unwanted metrics from increasing either the code 257size or object size of the metrics adapter, and by extension, 258:ref:`module-pw_allocator-api-tracking_allocator`. 259 260------- 261Roadmap 262------- 263While the :ref:`module-pw_allocator-api-allocator` interface is almost stable, 264there are some outstanding features the Pigweed team would like to add to 265``pw_allocator``: 266 267- **Asynchronous allocators**: Determine whether these should be provided, and 268 if so, add them. 269- **Additional smart pointers**: Determine if pointers like ``std::shared_ptr``, 270 etc., are needed, and if so, add them. 271- **Dynamic containers**: Provide the concept of allocator equality without 272 using RTTI or ``typeid``. This would allow dynamic containers with their own 273 allocators. 274- **Default allocators**: Integrate ``pw_allocator`` into the monolithic 275 ``pw_system`` as a starting point for projects. 276 277Found a bug? Got a feature request? Please create a new issue in our `tracker`_! 278 279Want to discuss allocators in real-time with the Pigweed team? Head over to our 280`Discord`_! 281 282.. _memory defects: https://en.wikipedia.org/wiki/Memory_corruption 283.. _golden hammer: https://en.wikipedia.org/wiki/Law_of_the_instrument#Computer_programming 284.. _bin packing problem: https://en.wikipedia.org/wiki/Bin_packing_problem 285.. _std::pmr::memory_resource: https://en.cppreference.com/w/cpp/memory/memory_resource 286.. _std::pmr::polymorphic_allocator: https://en.cppreference.com/w/cpp/memory/polymorphic_allocator 287.. _can use an allocator: https://en.cppreference.com/w/cpp/memory/uses_allocator 288.. _tracker: https://pwbug.dev 289.. _Discord: https://discord.gg/M9NSeTA 290