0110: Memory Allocation Interfaces#

Status: Open for Comments Intent Approved Last Call Accepted Rejected

Proposal Date: 2023-09-06

Author: 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#

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.

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 described below; 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.

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.

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.

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 Communication Buffers SEED.
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#

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?