| .. _module-pw_allocator-design: |
| |
| ================ |
| Design & roadmap |
| ================ |
| .. pigweed-module-subpage:: |
| :name: pw_allocator |
| |
| ---------------------------------- |
| Design of pw::allocator::Allocator |
| ---------------------------------- |
| Traditionally, most embedded firmware have laid out their systems’ memory usage |
| statically, with every component’s buffers and resources set at compile time. As |
| systems grow larger and more complex, dynamic allocation provides increasing |
| opportunities to simplify code and improve memory usage by enabling sharing and |
| eliminating large reservations. |
| |
| As a result, ``pw_allocator`` seeks to make dynamic allocation possible without |
| sacrificing too much of the control over memory usage that embedded developers |
| are accustomed to and need. The fundamental design goals of ``pw_allocator`` are |
| for allocators to be: |
| |
| - Familiar: The interface and its usage should resemble that of C++17's |
| `polymorphic allocators`_. |
| - Flexible: A diverse set of allocation strategies should be implementable |
| using allocators. |
| - Composable: Allocators should be able to combine and use other allocators. |
| - Extensible: Downstream projects should be able to provide their own allocator |
| implementations, and easily integrate them with Pigweed's. |
| - Cost-effective: Projects should be able to include only the allocator |
| behaviors they desire. |
| - Observable: Allocators should provide tools and data to reveal how memory is |
| being used. |
| - Correcting: Allocators should include features to help uncover |
| `memory defects`_ including heap corruption, leaks, use-after-frees, etc. |
| |
| Differences with C++ polymorphic allocators |
| =========================================== |
| C++17 introduced the ``<memory_resource>`` header with support for polymorphic |
| memory resources (PMR), i.e. allocators. This library defines many allocator |
| interfaces similar to those in ``pw_allocator``. |
| |
| Pigweed has decided to keep ``pw_allocator`` distinct from PMR primarily because |
| the latter's interface requires the use of C++ language features prohibited by |
| Pigweed. In PMR, allocators are expected to throw an exception in the case of |
| failure, and equality comparisons require runtime type identification (RTTI). |
| |
| Even so, ``pw_allocator`` has taken inspiration from the design of PMR, |
| incorporating many of its ideas. :ref:`module-pw_allocator-api-allocator` in |
| particular is similar to `std::pmr::memory_resource`_. |
| |
| .. TODO: b/328076428 - Furthermore, ``pw::allocator::MemoryResource`` acts as a |
| PMR adapter, allowing Pigweed allocators to be used with the C++ STL, albeit |
| at the cost of an extra layer of virtual indirection. |
| |
| .. _module-pw_allocator-design-forwarding: |
| |
| Forwarding allocator concept |
| ============================ |
| In addition to concrete allocator implementations, the design of |
| ``pw_allocator`` also encourages the use of "forwarding" allocators. These are |
| implementations of the :ref:`module-pw_allocator-api-allocator` interface that |
| don't allocate memory directly and instead rely on other allocators while |
| providing some additional behavior. |
| |
| For example, the :ref:`module-pw_allocator-api-allocator` records various |
| metrics such as the peak number of bytes allocated and the number of failed |
| allocation requests. It wraps another allocator which is used to actually |
| perform dynamic allocation. It implements the allocator API, and so it can be |
| passed into any routines that use dependency injection by taking a generic |
| :ref:`module-pw_allocator-api-allocator` parameter. |
| |
| These "forwarding" allocators are not completely free. At a miniumum, they |
| represent an extra virtual indirection, and an extra function call, albeit one |
| that can often be inlined. Additional behavior-specific code or state adds to |
| their cost in terms of code size and performance. Even so, these "forwarding" |
| allocators can provide savings relative to a "`golden hammer`_"-style allocator |
| that combined all of their features and more. By decomposing allocators into |
| orthogonal behaviors, implementers can choose to pay for only those that they |
| want. |
| |
| ----------------------------- |
| Design of allocator utilities |
| ----------------------------- |
| In addtion to providing allocator implementations themselves, ``pw_allocator`` |
| includes some foundational classes that can be used to implement allocators. |
| |
| .. _module-pw_allocator-design-block: |
| |
| pw::allocator::Block |
| ==================== |
| Several allocators make use of allocation metadata stored inline with the |
| allocations themselves. Often referred to as a "header", this metadata |
| immediately precedes the pointer to usable space returned by the allocator. This |
| header allows allocations to be variably sized, and converts allocation into a |
| `bin packing problem`_. An allocator that uses headers has a miniumum alignment |
| matching that of the header type itself. |
| |
| For ``pw_allocator``, the most common way to store this header is as a |
| :ref:`module-pw_allocator-api-block`. This class is used to construct a |
| doubly-linked list of subsequences of the allocator's memory region. It was |
| designed with the following features: |
| |
| - **Templated offset types**: Rather than use pointers to the next and previous |
| blocks, ``Block`` uses offsets of a templated unsigned integral type. This |
| saves a few bits that can be used for other purposes, since the blocks are |
| always aligned to the block header. It also gives callers the ability to |
| reduce the size of the headers if the allocator's memory region is |
| sufficently small, e.g. a type of ``uint16_t`` could be used if the region |
| could hold no more than 65536 block headers. |
| - **Splitting and merging**: This class centralizes the logic for splitting |
| memory regions into smaller pieces. Usable sub-blocks can either be split from |
| the beginning or end of a block. Additionally, blocks from either end can be |
| split at specified alignment boundaries. This class also provides the logic for |
| merging blocks back together. Together, these methods provide the invariant |
| that a free block is only ever adjacent to blocks in use. |
| - **Validation and poisoning**: On every deallocation, blocks validate their |
| metadata against their neighbors. A block can fail to be validated if it or |
| its neighbors have had their headers overwritten. In this case, it's unsafe to |
| continue to use this memory and the block code will assert in order make you |
| aware of the problem. Additionally, blocks can "paint" their memory with a |
| known poison pattern that's checked whenever the memory is next allocated. If |
| the check fails, then some code has written to unallocated memory. Again, the |
| block code will assert to alert you of a "use-after-free" condition. |
| |
| .. tip:: |
| In the case of memory corruption, the validation routines themsleves may |
| crash while attempting to inspect block headers. These crashes are not |
| exploitable from a security perspective, but lack the diagnostic information |
| from the usual ``PW_CHECK`` macro. Examining a stack trace may be helpful in |
| determining why validation failed. |
| |
| .. _module-pw_allocator-design-metrics: |
| |
| Allocator metrics |
| ================= |
| A common desire for a project using dynamic memory is to clearly understand how |
| much memory is being allocated. However, each tracked metric adds code size, |
| memory overhead, and a per-call performance cost. As a result, ``pw_allocator`` |
| is design to allow allocator implementers to select just the metrics they're |
| interested in. |
| |
| In particular, the :ref:`module-pw_allocator-api-metrics_adapter` uses |
| per-metric type traits generated by ``PW_ALLOCATOR_METRICS_DECLARE`` to |
| conditionally include the code to update the metrics that are included in its |
| ``MetricsType`` template parameter type. A suitable ``MetricType`` struct can be |
| created using the ``PW_ALLOCATOR_METRICS_ENABLE`` macro, which will only create |
| fields for the enabled metrics. |
| |
| Using these macros prevents unwanted metrics from increasing either the code |
| size or object size of the metrics adapter, and by extension, |
| :ref:`module-pw_allocator-api-tracking_allocator`. |
| |
| ------- |
| Roadmap |
| ------- |
| While the ``pw::allocator::Allocator`` interface is almost stable, there are |
| some outstanding features the Pigweed team would like to add to |
| ``pw_allocator``: |
| |
| - **Asynchronous allocators**: Determine whether these should be provided, and |
| if so, add them. |
| - **Additional smart pointers**: Determine if pointers like ``std::shared_ptr``, |
| etc., are needed, and if so, add them. |
| - **Dynamic containers**: Provide the concept of allocator equality without |
| using RTTI or ``typeid``. This would allow dynamic containers with their own |
| allocators. |
| - **Default allocators**: Integrate ``pw_allocator`` into the monolithic |
| ``pw_system`` as a starting point for projects. |
| |
| Found a bug? Got a feature request? Please create a new issue in our `tracker`_! |
| |
| Want to discuss allocators in real-time with the Pigweed team? Head over to our |
| `Discord`_! |
| |
| .. _polymorphic allocators: https://en.cppreference.com/w/cpp/memory/polymorphic_allocator |
| .. _memory defects: https://en.wikipedia.org/wiki/Memory_corruption |
| .. _golden hammer: https://en.wikipedia.org/wiki/Law_of_the_instrument#Computer_programming |
| .. _bin packing problem: https://en.wikipedia.org/wiki/Bin_packing_problem |
| .. _std::pmr::memory_resource: https://en.cppreference.com/w/cpp/memory/memory_resource |
| .. _tracker: https://pwbug.dev |
| .. _Discord: https://discord.gg/M9NSeTA |