| .. _seed-0110: |
| |
| ================================== |
| 0110: Memory Allocation Interfaces |
| ================================== |
| .. seed:: |
| :number: 110 |
| :name: Memory Allocation Interfaces |
| :status: Accepted |
| :proposal_date: 2023-09-06 |
| :cl: 168772 |
| :authors: Alexei Frolov |
| :facilitator: Taylor Cramer |
| |
| ------- |
| Summary |
| ------- |
| With dynamic memory allocation becoming more common in embedded devices, Pigweed |
| should provide standardized interfaces for working with different memory |
| allocators, giving both upstream and downstream developers the flexibility to |
| move beyond manually sizing their modules' resource pools. |
| |
| ---------- |
| Motivation |
| ---------- |
| 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, the ability to dynamically allocate |
| memory has become more desirable by firmware authors. |
| |
| Pigweed has made basic explorations into dynamic allocation in the past: the |
| ``pw_allocator`` provides basic building blocks which projects can use to |
| assemble their own allocators. ``pw_allocator`` also provides a proof-of-concept |
| allocator (``FreeListHeap``) based off of these building blocks. |
| |
| Since then, Pigweed has become a part of more complex projects and has |
| developed more advanced capabilities into its own modules. As the project has |
| progressed, several developers --- both on the core and customer teams --- have |
| noted areas where dynamic allocation would simplify code and improve memory |
| usage by enabling sharing and eliminating large reservations. |
| |
| -------- |
| Proposal |
| -------- |
| |
| Allocator Interfaces |
| ==================== |
| The core of the ``pw_allocator`` module will define abstract interfaces for |
| memory allocation. Several interfaces are provided with different allocator |
| properties, all of which inherit from a base generic ``Allocator``. |
| |
| Core Allocators |
| --------------- |
| |
| Allocator |
| ^^^^^^^^^ |
| |
| .. code-block:: c++ |
| |
| class Allocator { |
| public: |
| class Layout { |
| public: |
| constexpr Layout( |
| size_t size, std::align_val_t alignment = alignof(std::max_align_t)) |
| : size_(size), alignment_(alignment) {} |
| |
| // Creates a Layout for the given type. |
| template <typename T> |
| static constexpr Layout Of() { |
| return Layout(sizeof(T), alignof(T)); |
| } |
| |
| size_t size() const { return size_; } |
| size_t alignment() const { return alignment_; } |
| |
| private: |
| size_t size_; |
| size_t alignment_; |
| }; |
| |
| template <typename T, typename... Args> |
| T* New(Args&&... args); |
| |
| template <typename T> |
| void Delete(T* obj); |
| |
| template <typename T, typename... Args> |
| std::optional<UniquePtr<T>> MakeUnique(Args&&... args); |
| |
| void* Allocate(Layout layout) { |
| return DoAllocate(layout); |
| } |
| |
| void Deallocate(void* ptr, Layout layout) { |
| return DoDeallocate(layout); |
| } |
| |
| bool Resize(void* ptr, Layout old_layout, size_t new_size) { |
| if (ptr == nullptr) { |
| return false; |
| } |
| return DoResize(ptr, old_layout, new_size); |
| } |
| |
| void* Reallocate(void* ptr, Layout old_layout, size_t new_size) { |
| return DoReallocate(void* ptr, Layout old_layout, size_t new_size); |
| } |
| |
| protected: |
| virtual void* DoAllocate(Layout layout) = 0; |
| virtual void DoDeallocate(void* ptr, Layout layout) = 0; |
| |
| virtual bool DoResize(void* ptr, Layout old_layout, size_t new_size) { |
| return false; |
| } |
| |
| virtual void* DoReallocate(void* ptr, Layout old_layout, size_t new_size) { |
| if (new_size == 0) { |
| DoDeallocate(ptr, old_layout); |
| return nullptr; |
| } |
| |
| if (DoResize(ptr, old_layout, new_size)) { |
| return ptr; |
| } |
| |
| void* new_ptr = DoAllocate(new_layout); |
| if (new_ptr == nullptr) { |
| return nullptr; |
| } |
| |
| if (ptr != nullptr && old_layout.size() != 0) { |
| std::memcpy(new_ptr, ptr, std::min(old_layout.size(), new_size)); |
| DoDeallocate(ptr, old_layout); |
| } |
| |
| return new_ptr; |
| } |
| }; |
| |
| ``Allocator`` is the most generic and fundamental interface provided by the |
| module, representing any object capable of dynamic memory allocation. |
| |
| The ``Allocator`` interface makes no guarantees about its implementation. |
| Consumers of the generic interface must not make any assumptions around |
| allocator behavior, thread safety, or performance. |
| |
| **Layout** |
| |
| Allocation parameters are passed to the allocator through a ``Layout`` object. |
| This object ensures that the values provided to the allocator are valid, as well |
| as providing some convenient helper functions for common allocation use cases, |
| such as allocating space for a specific type of object. |
| |
| **Virtual functions** |
| |
| Implementers of the allocator interface are responsible for providing the |
| following operations: |
| |
| * ``DoAllocate`` (required): Obtains a block of memory from the allocator with a |
| requested size and power-of-two alignment. Returns ``nullptr`` if the |
| allocation cannot be performed. |
| |
| The size and alignment values in the provided layout are guaranteed to be |
| valid. |
| |
| Memory returned from ``DoAllocate`` is uninitialized. |
| |
| * ``DoDeallocate`` (required): Releases a block of memory back to the allocator. |
| |
| If ``ptr`` is ``nullptr``, does nothing. |
| |
| If ``ptr`` was not previously obtained from this allocator the behavior is |
| undefined. |
| |
| * ``DoResize`` (optional): Extends or shrinks a previously-allocated block of |
| memory in place. If this operation cannot be performed, returns ``false``. |
| |
| ``ptr`` is guaranteed to be non-null. If ``ptr`` was not previously obtained |
| from this allocator the behavior is undefined. |
| |
| If the allocated block is grown, the memory in the extended region is |
| uninitialized. |
| |
| * ``DoReallocate`` (optional): Extends or shrinks a previously-allocated block |
| of memory, potentially copying its data to a different location. A default |
| implementation is provided, which first attempts to call ``Resize``, falling |
| back to allocating a new block and copying data if it fails. |
| |
| If ``ptr`` is ``nullptr``, behaves identically to ``Allocate(new_layout)``. |
| |
| If the new block cannot be allocated, returns ``nullptr``, leaving the |
| original allocation intact. |
| |
| If ``new_layout.size == 0``, frees the old block and returns ``nullptr``. |
| |
| If the allocated block is grown, the memory in the extended region is |
| uninitialized. |
| |
| **Provided functions** |
| |
| * ``New``: Allocates memory for an object from the allocator and constructs it. |
| |
| * ``Delete``: Destructs and releases memory for a previously-allocated object. |
| |
| * ``MakeUnique``: Allocates and constructs an object wrapped in a ``UniquePtr`` |
| which owns it and manages its release. |
| |
| Allocator Utilities |
| =================== |
| In addition to allocator interfaces, ``pw_allocator`` will provide utilities for |
| working with allocators in a system. |
| |
| UniquePtr |
| --------- |
| ``pw::allocator::UniquePtr`` is a "smart pointer" analogous to |
| ``std::unique_ptr``, designed to work with Pigweed allocators. It owns and |
| manages an allocated object, automatically deallocating its memory when it goes |
| out of scope. |
| |
| Unlike ``std::unique_ptr``, Pigweed's ``UniquePtr`` cannot be manually |
| constructed from an existing non-null pointer; it must be done through the |
| ``Allocator::MakeUnique`` API. This is required as the allocator associated with |
| the object allocation must be known in order to release it. |
| |
| Usage reporting |
| --------------- |
| ``pw_allocator`` will not require any usage reporting as part of its core |
| interfaces to keep them minimal and reduce implementation burden. |
| |
| However, ``pw_allocator`` encourages setting up reporting and will provide |
| utilities for doing so. Initially, this consists of a layered proxy allocator |
| which wraps another allocator implementation with basic usage reporting through |
| ``pw_metric``. |
| |
| .. code-block:: c++ |
| |
| class AllocatorMetricProxy : public Allocator { |
| public: |
| constexpr explicit AllocatorMetricProxy(metric::Token token) |
| : memusage_(token) {} |
| |
| // Sets the wrapped allocator. |
| void Initialize(Allocator& allocator); |
| |
| // Exposed usage statistics. |
| metric::Group& memusage() { return memusage_; } |
| size_t used() const { return used_.value(); } |
| size_t peak() const { return peak_.value(); } |
| size_t count() const { return count_.value(); } |
| |
| // Implements the Allocator interface by forwarding through to the |
| // sub-allocator provided to Initialize. |
| |
| }; |
| |
| Integration with C++ polymorphic memory resources |
| ------------------------------------------------- |
| The C++ standard library has similar allocator interfaces to those proposed |
| defined as part of its PMR library. The reasons why Pigweed is not using these |
| directly are :ref:`described below <seed-0110-why-not-pmr>`; however, Pigweed |
| will provide a wrapper which exposes a Pigweed allocator through the PMR |
| ``memory_resource`` interface. An example of how this wrapper might look is |
| presented here. |
| |
| .. code-block:: c++ |
| |
| template <typename Allocator> |
| class MemoryResource : public std::pmr::memory_resource { |
| public: |
| template <typename... Args> |
| MemoryResource(Args&&... args) : allocator_(std::forward<Args>(args)...) {} |
| |
| private: |
| void* do_allocate(size_t bytes, size_t alignment) override { |
| void* p = allocator_.Allocate(bytes, alignment); |
| PW_ASSERT(p != nullptr); // Cannot throw in Pigweed code. |
| return p; |
| } |
| |
| void do_deallocate(void* p, size_t bytes, size_t alignment) override { |
| allocator_.Deallocate(p, bytes, alignment); |
| } |
| |
| bool do_is_equal(const std::pmr::memory_resource&) override { |
| // Pigweed allocators do not yet support the concept of equality; this |
| // remains an open question for the future. |
| return false; |
| } |
| |
| Allocator allocator_; |
| }; |
| |
| Future Considerations |
| ===================== |
| |
| Allocator traits |
| ---------------- |
| It can be useful for users to know additional details about a specific |
| implementation of an allocator to determine whether it is suitable for their |
| use case. For example, some allocators may have internal synchronization, |
| removing the need for external locking. Certain allocators may be suitable for |
| uses in specialized contexts such as interrupts. |
| |
| To enable users to enforce these types of requirements, it would be useful to |
| provide a way for allocator implementations to define certain traits. |
| Originally, this proposal accommodated for this by defining derived allocator |
| interfaces which semantically enforced additional implementation contracts. |
| However, this approach could have led to an explosion of different allocator |
| types throughout the codebase for each permutation of traits. As such, it was |
| removed from the initial allocator plan for future reinvestigation. |
| |
| Dynamic collections |
| ------------------- |
| The ``pw_containers`` module defines several collections such as ``pw::Vector``. |
| These collections are modeled after STL equivalents, though being |
| embedded-friendly, they reserve a fixed maximum size for their elements. |
| |
| With the addition of dynamic allocation to Pigweed, these containers will be |
| expanded to support the use of allocators. Unless absolutely necessary, upstream |
| containers should be designed to work on the base ``Allocator`` interface --- |
| not any of its derived classes --- to offer maximum flexibility to projects |
| using them. |
| |
| .. code-block:: c++ |
| |
| template <typename T> |
| class DynamicVector { |
| DynamicVector(Allocator& allocator); |
| }; |
| |
| Per-allocation tagging |
| ---------------------- |
| Another interface which was originally proposed but shelved for the time being |
| allowed for the association of an integer tag with each specific call to |
| ``Allocate``. This can be incredibly useful for debugging, but requires |
| allocator implementations to store additional information with each allocation. |
| This added complexity to allocators, so it was temporarily removed to focus on |
| refining the core allocator interface. |
| |
| The proposed 32-bit integer tags happen to be the same as the tokens generated |
| from strings by the ``pw_tokenizer`` module. Combining the two could result in |
| the ability to precisely track the source of allocations in a project. |
| |
| For example, ``pw_allocator`` could provide a macro which tokenizes a user |
| string to an allocator tag, automatically inserting additional metadata such as |
| the file and line number of the allocation. |
| |
| .. code-block:: c++ |
| |
| void GenerateAndProcessData(TaggedAllocator& allocator) { |
| void* data = allocator->AllocatedTagged( |
| Layout::Sized(kDataSize), PW_ALLOCATOR_TAG("my data buffer")); |
| if (data == nullptr) { |
| return; |
| } |
| |
| GenerateData(data); |
| ProcessData(data); |
| |
| allocator->Deallocate(data); |
| } |
| |
| Allocator implementations |
| ------------------------- |
| Over time, Pigweed expects to implement a handful of different allocators |
| covering the interfaces proposed here. No specific new implementations are |
| suggested as part of this proposal. Pigweed's existing ``FreeListHeap`` |
| allocator will be refactored to implement the ``Allocator`` interface. |
| |
| --------------------- |
| Problem Investigation |
| --------------------- |
| |
| Use cases and requirements |
| ========================== |
| |
| * **General-purpose memory allocation.** The target of ``pw_allocator`` is |
| general-purpose dynamic memory usage by typical applications, rather than |
| specialized types of memory allocation that may be required by lower-level |
| code such as drivers. |
| |
| * **Generic interfaces with minimal policy.** Every project has different |
| resources and requirements, and particularly in constrained systems, memory |
| management is often optimized for their specific use cases. Pigweed's core |
| allocation interfaces should offer as broad of an implementation contract as |
| possible and not bake in assumptions about how they will be run. |
| |
| * **RTOS or bare metal usage.** While many systems make use of an RTOS which |
| provides utilities such as threads and synchronization primitives, Pigweed |
| also targets systems which run without one. As such, the core allocators |
| should not be tied to any RTOS requirements, and accommodations should be made |
| for different system contexts. |
| |
| Out of scope |
| ------------ |
| |
| * **Asynchronous allocation.** As this proposal is centered around simple |
| general-purpose allocation, it does not consider asynchronous allocations. |
| While these are important use cases, they are typically more specialized and |
| therefore outside the scope of this proposal. Pigweed is considering some |
| forms of asynchronous memory allocation, such as the proposal in the |
| :ref:`Communication Buffers SEED <seed-0109>`. |
| |
| * **Direct STL integration.** The C++ STL makes heavy use of dynamic memory and |
| offers several ways for projects to plug in their own allocators. This SEED |
| does not propose any direct Pigweed to STL-style allocator adapters, nor does |
| it offer utilities for replacing the global ``new`` and ``delete`` operators. |
| These are additions which may come in future changes. |
| |
| It is still possible to use Pigweed allocators with the STL in an indirect way |
| by going through the PMR interface, which is discussed later. |
| |
| * **Global Pigweed allocators.** Pigweed modules will not assume a global |
| allocator instantiation. Any usage of allocators by modules should rely on |
| dependency injection, leaving consumers with control over how they choose to |
| manage their memory usage. |
| |
| Alternative solutions |
| ===================== |
| |
| .. _seed-0110-why-not-pmr: |
| |
| 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 this proposal. Naturally, this raises the |
| question of whether Pigweed can use them directly, benefitting from the larger |
| C++ ecosystem. |
| |
| The primary issue with PMR with regards to Pigweed is that the interfaces |
| require the use of C++ language features prohibited by Pigweed. The allocator |
| is expected to throw an exception in the case of failure, and equality |
| comparisons require RTTI. The team is not prepared to change or make exceptions |
| to this policy, prohibiting the direct usage of PMR. |
| |
| Despite this, Pigweed's allocator interfaces have taken inspiration from the |
| design of PMR, incorporating many of its ideas. The core proposed ``Allocator`` |
| interface is similar to ``std::pmr::memory_resource``, making it possible to |
| wrap Pigweed allocators with a PMR adapter for use with the C++ STL, albeit at |
| the cost of an extra layer of virtual indirection. |
| |
| -------------- |
| Open Questions |
| -------------- |
| This SEED proposal is only a starting point for the improvement of the |
| ``pw_allocator`` module, and Pigweed's memory management story in general. |
| |
| There are several open questions around Pigweed allocators which the team |
| expects to answer in future SEEDs: |
| |
| * Should generic interfaces for asynchronous allocations be provided, and how |
| would they look? |
| |
| * Reference counted allocations and "smart pointers": where do they fit in? |
| |
| * The concept of allocator equality is essential to enable certain use cases, |
| such as efficiently using dynamic containers with their own allocators. |
| This proposal excludes APIs paralleling PMR's ``is_equal`` due to RTTI |
| requirements. Could Pigweed allocators implement a watered-down version of an |
| RTTI / type ID system to support this? |
| |
| * How do allocators integrate with the monolithic ``pw_system`` as a starting |
| point for projects? |