diff options
Diffstat (limited to 'seed/0110-memory-allocation-interfaces.rst')
| -rw-r--r-- | seed/0110-memory-allocation-interfaces.rst | 464 |
1 files changed, 464 insertions, 0 deletions
diff --git a/seed/0110-memory-allocation-interfaces.rst b/seed/0110-memory-allocation-interfaces.rst new file mode 100644 index 000000000..931cf6391 --- /dev/null +++ b/seed/0110-memory-allocation-interfaces.rst @@ -0,0 +1,464 @@ +.. _seed-0110: + +================================== +0110: Memory Allocation Interfaces +================================== +.. seed:: + :number: 110 + :name: Memory Allocation Interfaces + :status: Accepted + :proposal_date: 2023-09-06 + :cl: 168772 + +------- +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? |