Guides#

pw_allocator: Flexible, safe, and measurable memory allocation

Get started#

Bazel

Add @pigweed//pw_allocator to the deps list in your Bazel target:

cc_library("...") {
  # ...
  deps = [
    # ...
    "@pigweed//pw_allocator",
    # ...
  ]
}

For a narrower dependency, depend on subtargets, e.g. @pigweed//pw_allocator:tracking_allocator.

This assumes @pigweed is the name you pulled Pigweed into your Bazel WORKSPACE as.

This assumes that your Bazel WORKSPACE has a repository named @pigweed that points to the upstream Pigweed repository.

Add dir_pw_allocator to the deps list in your build target:

pw_executable("...") {
  # ...
  deps = [
    # ...
    dir_pw_allocator,
    # ...
  ]
}

For a narrower dependency, depend on subtargets, e.g. "$dir_pw_allocator:tracking_allocator".

If the build target is a dependency of other targets and includes allocators in its public interface, e.g. its header file, use public_deps instead of deps.

CMake

Add pw_allocator to your pw_add_library or similar CMake target:

pw_add_library(my_library STATIC
  HEADERS
    ...
  PRIVATE_DEPS
    # ...
    pw_allocator
    # ...
)

For a narrower dependency, depend on subtargets, e.g. pw_allocator.tracking_allocator, etc.

If the build target is a dependency of other targets and includes allocators in its public interface, e.g. its header file, use PUBLIC_DEPS instead of PRIVATE_DEPS.

Inject allocators#

Routines that need to allocate memory dynamically should do so using the generic Allocator interface. By using dependency injection, memory users can be kept decoupled from the details of how memory is provided. This yields the most flexibility for modifying or replacing the specific allocators.

Use the `Allocator` interface#

Write or refactor your memory-using routines to take a pointer or reference to such an object and use the Allocate, Deallocate, Reallocate, and Resize methods to manage memory. For example:

using pw::allocator::Allocator;
using pw::allocator::Layout;

void* AllocateNamedU32(Allocator& allocator) {
  return allocator.Allocate(Layout::Of<NamedU32>());
}

void DeallocateNamedU32(Allocator& allocator, void* ptr) {
  allocator.Deallocate(ptr);
}

To invoke methods or objects that inject allocators now requires an allocator to have been constructed. The exact location where allocators should be instantiated will vary from project to project, but it’s likely to be early in a program’s lifecycle and in a device-specific location of the source tree.

For initial testing on host, a simple allocator such as LibCAllocator can be used. This allocator is trivally constructed and simply wraps malloc and free.

Use New and Delete#

In addition to managing raw memory, an Allocator can also be used to create and destroy objects:

NamedU32* NewNamedU32(Allocator& allocator,
                      std::string_view name,
                      uint32_t value) {
  return allocator.New<NamedU32>(name, value);
}

void DeleteNamedU32(Allocator& allocator, NamedU32* named_u32) {
  allocator.Delete<NamedU32>(named_u32);
}

Use UniquePtr<T>#

Where possible, using RAII is a recommended approach for making memory management easier and less error-prone. UniquePtr is a smart pointer that makes allocating and deallocating memory more transparent:

pw::allocator::UniquePtr<NamedU32> MakeNamedU32(Allocator& allocator,
                                                std::string_view name,
                                                uint32_t value) {
  return allocator.MakeUnique<NamedU32>(name, value);
}

Determine an allocation’s Layout#

Several of the Allocator methods take a parameter of the Layout type. This type combines the size and alignment requirements of an allocation. It can be constructed directly, or if allocating memory for a specific type, by using a templated static method:

template <typename T, typename... Args>
T* my_new(Args... args) {
  void* ptr = allocator.Allocate(pw::allocator::Layout::Of<T>());
  return ptr == nullptr ? nullptr : new (ptr) T(std::forward<Args>(args)...);
}

As stated above, you should generally try to keep allocator implementation details abstracted behind the Allocator interface. One exception to this guidance is when integrating allocators into existing code that assumes malloc and free semantics. Notably, free does not take any parameters beyond a pointer describing the memory to be freed. To implement such a method using Deallocate, you may need to violate the abstraction and only use allocators that implement the optional GetLayout method:

void* my_malloc(size_t size) {
  return allocator.Allocate(
      pw::allocator::Layout(size, alignof(std::max_align_t)));
}

void my_free(void* ptr) { allocator.Deallocate(ptr); }

Choose the right allocator#

Once one or more routines are using allocators, you can consider how best to implement memory allocation for each particular scenario.

Concrete allocator implementations#

This module provides several allocator implementations. The following is an overview. Consult the API reference for additional details.

LibCAllocator: Uses malloc, realloc, and free. This should only be used if the libc in use provides those functions.
NullAllocator: Always fails. This may be useful if allocations should be disallowed under specific circumstances.
BumpAllocator: Allocates objects out of a region of memory and only frees them all at once when the allocator is destroyed.
BuddyAllocator: Allocates objects out of a chunks with sizes that are powers of two. Chunks are split evenly for smaller allocations and merged on free.
BlockAllocator: Tracks memory using Block. Derived types use specific strategies for how to choose a block to use to satisfy a request. See also pw::allocator::Block. Derived types include:
- FirstFitBlockAllocator: Chooses the first block that’s large enough to satisfy a request. This strategy is very fast, but may increase fragmentation.
- LastFitBlockAllocator: Chooses the last block that’s large enough to satisfy a request. This strategy is fast, and may fragment memory less than FirstFitBlockAllocator when satisfying aligned memory requests.
- BestFitBlockAllocator: Chooses the smallest block that’s large enough to satisfy a request. This strategy maximizes the avilable space for large allocations, but may increase fragmentation and is slower.
- WorstFitBlockAllocator: Chooses the largest block if it’s large enough to satisfy a request. This strategy minimizes the amount of memory in unusably small blocks, but is slower.
- DualFirstFitBlockAllocator: Acts like FirstFitBlockAllocator or LastFitBlockAllocator depending on whether a request is larger or smaller, respectively, than a given threshold value. This strategy preserves the speed of the two other strategies, while fragmenting memory less by co-locating allocations of similar sizes.
TypedPool: Efficiently creates and destroys objects of a single given type.

Forwarding allocator implementations#

This module provides several “forwarding” allocators, as described in Forwarding allocator concept. The following is an overview. Consult the API reference for additional details.

FallbackAllocator: Dispatches first to a primary allocator, and, if that fails, to a secondary allocator.
SynchronizedAllocator: Synchronizes access to another allocator, allowing it to be used by multiple threads.
TrackingAllocator: Wraps another allocator and records its usage.

Custom allocator implementations#

If none of the allocator implementations provided by this module meet your needs, you can implement your allocator and pass it into any routine that uses the generic interface.

Allocator uses an NVI pattern. To add a custom allocator implementation, you must at a miniumum implement the DoAllocate and DoDeallocate methods.

For example, the following is a forwarding allocator that simply writes to the log whenever a threshold is exceeded:

#include <cstddef>

#include "pw_allocator/allocator.h"

namespace examples {

class CustomAllocator : public pw::allocator::Allocator {
 public:
  using Allocator = pw::allocator::Allocator;
  using Layout = pw::allocator::Layout;

  CustomAllocator(Allocator& allocator, size_t threshold);

 private:
  /// @copydoc pw::allocator::Allocator::Allocate
  void* DoAllocate(Layout layout) override;

  /// @copydoc pw::allocator::Allocator::Deallocate
  void DoDeallocate(void* ptr) override;

  /// @copydoc pw::allocator::Allocator::Deallocate
  void DoDeallocate(void* ptr, Layout) override { DoDeallocate(ptr); }

  Allocator& allocator_;
  size_t used_ = 0;
  size_t threshold_ = 0;
};

}  // namespace examples

#include "examples/custom_allocator.h"

#include <cstdint>

#include "pw_allocator/capability.h"
#include "pw_log/log.h"
#include "pw_result/result.h"

namespace examples {

CustomAllocator::CustomAllocator(Allocator& allocator, size_t threshold)
    : Allocator(pw::allocator::Capabilities()),
      allocator_(allocator),
      threshold_(threshold) {}

// Allocates, and reports if allocated memory exceeds its threshold.
void* CustomAllocator::DoAllocate(Layout layout) {
  void* ptr = allocator_.Allocate(layout);
  if (ptr == nullptr) {
    return nullptr;
  }
  size_t prev = used_;
  pw::Result<Layout> allocated = GetAllocatedLayout(allocator_, ptr);
  if (allocated.ok()) {
    used_ += allocated->size();
  }
  if (prev <= threshold_ && threshold_ < used_) {
    PW_LOG_INFO("more than %zu bytes allocated.", threshold_);
  }
  return ptr;
}

void CustomAllocator::DoDeallocate(void* ptr) {
  if (ptr == nullptr) {
    return;
  }
  pw::Result<Layout> allocated = GetAllocatedLayout(allocator_, ptr);
  if (allocated.ok()) {
    used_ -= allocated->size();
  }
  allocator_.Deallocate(ptr);
}

}  // namespace examples

There are also several optional methods you can provide:

If an implementation of DoResize isn’t provided, then Resize will always return false.
If an implementation of DoReallocate isn’t provided, then Reallocate will try to Resize, and, if unsuccessful, try to Allocate, copy, and Deallocate.
If an implementation of DoGetLayout isn’t provided, then GetLayout will always return pw::Status::Unimplmented.
If an implementation of DoQuery isn’t provided, then Query will always return pw::Status::Unimplmented.

Custom allocators can indicate which optional methods they implement and what optional behaviors they want from the base class by specifying Capabilities when invoking the base class constructor.

Measure memory usage#

You can observe how much memory is being used for a particular use case using a TrackingAllocator.

struct CustomMetrics {
  PW_ALLOCATOR_METRICS_ENABLE(allocated_bytes);
  PW_ALLOCATOR_METRICS_ENABLE(peak_allocated_bytes);
  PW_ALLOCATOR_METRICS_ENABLE(num_failures);
};

  constexpr pw::metric::Token kToken = PW_TOKENIZE_STRING("CustomMetrics");
  pw::allocator::TrackingAllocatorImpl<CustomMetrics> tracker(kToken,
                                                              allocator);

Metric data can be retrieved according to the steps described in Exporting metrics, or by using the Dump method of Group:

  tracker.metric_group().Dump();

The CustomMetrics type used in the example above is a struct provided by the developer. You can create your own metrics structs that enable zero or more of the following metrics:

requested_bytes: The number of bytes currently requested from this allocator.
peak_requested_bytes: The most bytes requested from this allocator at any one time.
cumulative_requested_bytes: The total number of bytes that have been requested from this allocator across its lifetime.
allocated_bytes: The number of bytes currently allocated by this allocator.
peak_allocated_bytes: The most bytes allocated by this allocator at any one time.
cumulative_allocated_bytes: The total number of bytes that have been allocated by this allocator across its lifetime.
num_allocations: The number of allocation requests this allocator has successfully completed.
num_deallocations: The number of deallocation requests this allocator has successfully completed.
num_resizes: The number of resize requests this allocator has successfully completed.
num_reallocations: The number of reallocation requests this allocator has successfully completed.
num_failures: The number of requests this allocator has failed to complete.

If you only want a subset of these metrics, you can implement your own metrics struct. For example:

struct CustomMetrics {
  PW_ALLOCATOR_METRICS_ENABLE(allocated_bytes);
  PW_ALLOCATOR_METRICS_ENABLE(peak_allocated_bytes);
  PW_ALLOCATOR_METRICS_ENABLE(num_failures);
};

If you have multiple routines that share an underlying allocator that you want to track separately, you can create multiple tracking allocators that forward to the same underlying allocator:

  using MyTrackingAllocator =
      pw::allocator::TrackingAllocatorImpl<pw::allocator::internal::AllMetrics>;

  constexpr pw::metric::Token kToken0 = PW_TOKENIZE_STRING("Combined");
  MyTrackingAllocator combined(kToken0, allocator);

  constexpr pw::metric::Token kToken1 = PW_TOKENIZE_STRING("Tracker1");
  MyTrackingAllocator tracker1(kToken1, combined);

  constexpr pw::metric::Token kToken2 = PW_TOKENIZE_STRING("Tracker2");
  MyTrackingAllocator tracker2(kToken2, combined);

  combined.metric_group().Add(tracker1.metric_group());
  combined.metric_group().Add(tracker2.metric_group());

Detect memory corruption#

The pw::allocator::Block class provides a few different mechanisms to help detect memory corruptions when they happen. First, on every deallocation it will check the integrity of the block header and assert if it has been modified.

Additionally, you can enable poisoning to detect additional memory corruptions such as use-after-frees. The Block type has a template parameter that enables the Poison and CheckPoison methods. Allocators can use these methods to “poison” blocks on deallocation with a set pattern, and later check on allocation that the pattern is intact. If it’s not, some routine has modified unallocated memory.

The BlockAllocator class has a kPoisonInterval template parameter to control how frequently blocks are poisoned on deallocation. This allows projects to stochiastically sample allocations for memory corruptions while mitigating the performance impact.

// Poisons every third deallocation.
pw::allocator::LastFitBlockAllocator<uint16_t, 3> allocator(buffer);

Test custom allocators#

If you create your own allocator implementation, it’s strongly recommended that you test it as well. If you’re creating a forwarding allocator, you can use AllocatorForTest. This simple allocator provides its own backing storage and automatically frees any outstanding allocations when it goes out of scope. It also tracks the most recent values provided as parameters to the interface methods.

For example, the following tests the custom allocator from Custom allocator implementations:

// TODO: b/328076428 - Use pwrev/193642.
TEST(CustomAllocatorExample, MakeUnique) {
  test::AllocatorForTest<256> allocator;
  constexpr size_t kThreshold = sizeof(examples::NamedU32) * 3;
  examples::CustomAllocator custom(allocator, kThreshold);
  // log_basic::test::LogCache<32> logs;

  auto ptr1 = custom.MakeUnique<examples::NamedU32>("test", 111);
  auto ptr2 = custom.MakeUnique<examples::NamedU32>("test", 222);
  auto ptr3 = custom.MakeUnique<examples::NamedU32>("test", 333);
  // EXPECT_FALSE(logs.HasNext());

  auto ptr4 = custom.MakeUnique<examples::NamedU32>("test", 444);
  // ASSERT_TRUE(logs.HasNext());
  // log_basic::test::LogMessage log = logs.Next();
  // EXPECT_EQ(log.level, PW_LOG_LEVEL_INFO);

  // StringBuffer<40> expected;
  // expected << "more than " << kThreshold << " bytes allocated.";
  // EXPECT_STREQ(log.message.c_str(), expected.c_str());
}

You can also extend the AllocatorTestHarness to perform pseudorandom sequences of allocations and deallocations, e.g. as part of a performance test:

#include <cstddef>

#include "examples/custom_allocator.h"
#include "pw_allocator/test_harness.h"
#include "pw_allocator/testing.h"

namespace examples {

class CustomAllocatorTestHarness
    : public pw::allocator::test::AllocatorTestHarness<64> {
 public:
  static constexpr size_t kCapacity = 0x1000;
  static constexpr size_t kThreshold = 0x800;

  CustomAllocatorTestHarness() : custom_(allocator_, kThreshold) {}
  ~CustomAllocatorTestHarness() override = default;

  pw::allocator::Allocator* Init() override { return &custom_; }

 private:
  pw::allocator::test::AllocatorForTest<kCapacity> allocator_;
  CustomAllocator custom_;
};

}  // namespace examples

#include <cstdint>

#include "examples/custom_allocator_test_harness.h"
#include "pw_perf_test/perf_test.h"
#include "pw_perf_test/state.h"
#include "pw_random/xor_shift.h"

namespace examples {

void PerformAllocations(pw::perf_test::State& state, uint64_t seed) {
  static CustomAllocatorTestHarness harness;
  pw::random::XorShiftStarRng64 prng(seed);
  while (state.KeepRunning()) {
    harness.GenerateRequest(prng, CustomAllocatorTestHarness::kCapacity);
  }
  harness.Reset();
}

PW_PERF_TEST(CustomAllocatorPerfTest, PerformAllocations, 1);

}  // namespace examples

Even better, you can easily add fuzz tests for your allocator. This module uses the AllocatorTestHarness to integrate with pw_fuzzer and provide FuzzTest support.

void NeverCrashes(const Vector<test::AllocatorRequest>& requests) {
  static examples::CustomAllocatorTestHarness harness;
  harness.HandleRequests(requests);
}

constexpr size_t kMaxRequests = 256;
constexpr size_t kMaxSize = examples::CustomAllocatorTestHarness::kCapacity / 2;
FUZZ_TEST(CustomAllocatorFuzzTest, NeverCrashes)
    .WithDomains(test::ArbitraryAllocatorRequests<kMaxRequests, kMaxSize>());

Measure custom allocator size#

If you create your own allocator implementation, you may wish to measure its code size, similar to measurements in the module’s own Code size analysis. You can use pw_bloat and SizeReporter to create size reports as described in Defining size reports in GN.

For example, the C++ code for a size report binary might look like:

#include <cstdint>

#include "examples/custom_allocator.h"
#include "pw_allocator/block_allocator.h"
#include "pw_allocator/size_reporter.h"

int main() {
  pw::allocator::SizeReporter reporter;
  reporter.SetBaseline();

  pw::allocator::FirstFitBlockAllocator<uint16_t> allocator(reporter.buffer());
  examples::CustomAllocator custom(allocator, 128);
  reporter.Measure(custom);

  return 0;
}

The resulting binary could be compared with the binary produced from pw_allocator/size_report/first_fit_block_allocator.cc to identify just the code added in this case by CustomAllocator.

For example, the GN build rule to generate a size report might look liek:

pw_size_diff("size_report") {
  title = "Example size report"
  binaries = [
    {
      target = ":size_report"
      base = "$dir_pw_allocator/size_report:first_fit_block_allocator"
      label = "CustomAllocator"
    },
  ]
}

The size report produced by this rule would render as:

Label

Segment

Delta

CustomAllocator

+272