1.. _module-pw_allocator-guides: 2 3====== 4Guides 5====== 6.. pigweed-module-subpage:: 7 :name: pw_allocator 8 9.. _module-pw_allocator-get-started: 10 11----------- 12Get started 13----------- 14.. tab-set:: 15 16 .. tab-item:: Bazel 17 18 Add ``@pigweed//pw_allocator`` to the ``deps`` list in your Bazel target: 19 20 .. code-block:: 21 22 cc_library("...") { 23 # ... 24 deps = [ 25 # ... 26 "@pigweed//pw_allocator", 27 # ... 28 ] 29 } 30 31 For a narrower dependency, depend on subtargets, e.g. 32 ``@pigweed//pw_allocator:tracking_allocator``. 33 34 This assumes ``@pigweed`` is the name you pulled Pigweed into your Bazel 35 ``WORKSPACE`` as. 36 37 This assumes that your Bazel ``WORKSPACE`` has a `repository`_ named 38 ``@pigweed`` that points to the upstream Pigweed repository. 39 40 .. tab-item:: GN 41 42 Add ``dir_pw_allocator`` to the ``deps`` list in your build target: 43 44 .. code-block:: 45 46 pw_executable("...") { 47 # ... 48 deps = [ 49 # ... 50 dir_pw_allocator, 51 # ... 52 ] 53 } 54 55 For a narrower dependency, depend on subtargets, e.g. 56 ``"$dir_pw_allocator:tracking_allocator"``. 57 58 If the build target is a dependency of other targets and includes 59 allocators in its public interface, e.g. its header file, use 60 ``public_deps`` instead of ``deps``. 61 62 .. tab-item:: CMake 63 64 Add ``pw_allocator`` to your ``pw_add_library`` or similar CMake target: 65 66 .. code-block:: 67 68 pw_add_library(my_library STATIC 69 HEADERS 70 ... 71 PRIVATE_DEPS 72 # ... 73 pw_allocator 74 # ... 75 ) 76 77 For a narrower dependency, depend on subtargets, e.g. 78 ``pw_allocator.tracking_allocator``, etc. 79 80 If the build target is a dependency of other targets and includes 81 allocators in its public interface, e.g. its header file, use 82 ``PUBLIC_DEPS`` instead of ``PRIVATE_DEPS``. 83 84.. _module-pw_allocator-module-configuration: 85 86-------------------- 87Module configuration 88-------------------- 89This module has configuration options that globally affect the behavior of 90``pw_allocator`` via compile-time configuration of this module, see the 91:ref:`module documentation <module-structure-compile-time-configuration>` for 92more details. 93 94.. doxygendefine:: PW_ALLOCATOR_STRICT_VALIDATION 95.. doxygendefine:: PW_ALLOCATOR_BLOCK_POISON_INTERVAL 96 97----------------- 98Inject allocators 99----------------- 100Routines that need to allocate memory dynamically should do so using the generic 101:ref:`module-pw_allocator-api-allocator` interface. By using dependency 102injection, memory users can be kept decoupled from the details of how memory is 103provided. This yields the most flexibility for modifying or replacing the 104specific allocators. 105 106Use the ``Allocator`` interface 107=============================== 108Write or refactor your memory-using routines to take 109a pointer or reference to such an object and use the ``Allocate``, 110``Deallocate``, ``Reallocate``, and ``Resize`` methods to manage memory. For 111example: 112 113.. literalinclude:: examples/basic.cc 114 :language: cpp 115 :linenos: 116 :start-after: [pw_allocator-examples-basic-allocate] 117 :end-before: [pw_allocator-examples-basic-allocate] 118 119.. literalinclude:: examples/basic.cc 120 :language: cpp 121 :linenos: 122 :start-after: [pw_allocator-examples-basic-deallocate] 123 :end-before: [pw_allocator-examples-basic-deallocate] 124 125To invoke methods or objects that inject allocators now requires an allocator to 126have been constructed. The exact location where allocators should be 127instantiated will vary from project to project, but it's likely to be early in a 128program's lifecycle and in a device-specific location of the source tree. 129 130For initial testing on :ref:`target-host`, a simple allocator such as 131:ref:`module-pw_allocator-api-libc_allocator` can be used. This allocator is 132trivally constructed and simply wraps ``malloc`` and ``free``. 133 134Use New and Delete 135================== 136In addition to managing raw memory, an ``Allocator`` can also be used to create 137and destroy objects: 138 139.. literalinclude:: examples/basic.cc 140 :language: cpp 141 :linenos: 142 :start-after: [pw_allocator-examples-basic-new_delete] 143 :end-before: [pw_allocator-examples-basic-new_delete] 144 145Use UniquePtr<T> 146================ 147Where possible, using `RAII`_ is a recommended approach for making memory 148management easier and less error-prone. 149:ref:`module-pw_allocator-api-unique_ptr` is a smart pointer that makes 150allocating and deallocating memory more transparent: 151 152.. literalinclude:: examples/basic.cc 153 :language: cpp 154 :linenos: 155 :start-after: [pw_allocator-examples-basic-make_unique] 156 :end-before: [pw_allocator-examples-basic-make_unique] 157 158Determine an allocation's Layout 159================================ 160Several of the :ref:`module-pw_allocator-api-allocator` methods take a parameter 161of the :ref:`module-pw_allocator-api-layout` type. This type combines the size 162and alignment requirements of an allocation. It can be constructed directly, or 163if allocating memory for a specific type, by using a templated static method: 164 165.. literalinclude:: examples/block_allocator.cc 166 :language: cpp 167 :linenos: 168 :start-after: [pw_allocator-examples-block_allocator-layout_of] 169 :end-before: [pw_allocator-examples-block_allocator-layout_of] 170 171As stated above, you should generally try to keep allocator implementation 172details abstracted behind the :ref:`module-pw_allocator-api-allocator` 173interface. One exception to this guidance is when integrating allocators into 174existing code that assumes ``malloc`` and ``free`` semantics. Notably, ``free`` 175does not take any parameters beyond a pointer describing the memory to be freed. 176 177.. literalinclude:: examples/block_allocator.cc 178 :language: cpp 179 :linenos: 180 :start-after: [pw_allocator-examples-block_allocator-malloc_free] 181 :end-before: [pw_allocator-examples-block_allocator-malloc_free] 182 183.. _module-pw_allocator-use-standard-library-containers: 184 185Use standard library containers 186=============================== 187All of C++'s standard library containers are `AllocatorAwareContainers`_, with 188the exception of ``std::array``. These types include a template parameter used 189to specify an allocator type, and a constructor which takes a reference to an 190object of this type. 191 192While there are 193:ref:`module-pw_allocator-design-differences-with-polymorphic-allocators`, an 194:ref:`module-pw_allocator-api-allocator` can be used with these containers by 195wrapping them with a PMR adapter type, 196:ref:`module-pw_allocator-api-pmr_allocator`: 197 198.. literalinclude:: examples/pmr.cc 199 :language: cpp 200 :linenos: 201 :start-after: [pw_allocator-examples-pmr] 202 :end-before: [pw_allocator-examples-pmr] 203 204.. Warning:: 205 Some of the standard library containers may add a significant amount of 206 additional code size and/or memory overhead. In particular, implementations 207 of ``std::deque`` are known to preallocate significant memory in order to 208 meet its complexity requirements, e.g. O(1) insertion at the front of the 209 deque. 210 211.. Warning:: 212 The standard library containers expect their allocators to throw an exception 213 on allocation failure, and do not check for failure themselves. If 214 exceptions are disabled, :ref:`module-pw_allocator-api-pmr_allocator` 215 instead **asserts** that allocation succeeded. Care must be taken in this 216 case to ensure that memory is not exhausted. 217 218-------------------------- 219Choose the right allocator 220-------------------------- 221Once one or more routines are using allocators, you can consider how best to 222implement memory allocation for each particular scenario. 223 224.. TODO(b/378549332): Add a decision tree for selecting an allocator. 225 226Concrete allocator implementations 227================================== 228This module provides several allocator implementations. The following is an 229overview. Consult the :ref:`module-pw_allocator-api` for additional details. 230 231- :ref:`module-pw_allocator-api-libc_allocator`: Uses ``malloc``, ``realloc``, 232 and ``free``. This should only be used if the ``libc`` in use provides those 233 functions. This allocator is a stateless singleton that may be referenced 234 using ``GetLibCAllocator()``. 235- :ref:`module-pw_allocator-api-null_allocator`: Always fails. This may be 236 useful if allocations should be disallowed under specific circumstances. 237 This allocator is a stateless singleton that may be referenced using 238 ``GetNullAllocator()``. 239- :ref:`module-pw_allocator-api-bump_allocator`: Allocates objects out of a 240 region of memory and only frees them all at once when the allocator is 241 destroyed. 242- :ref:`module-pw_allocator-api-buddy_allocator`: Allocates objects out of a 243 blocks with sizes that are powers of two. Blocks are split evenly for smaller 244 allocations and merged on free. 245- :ref:`module-pw_allocator-api-block_allocator`: Tracks memory using 246 :ref:`module-pw_allocator-api-block`. Derived types use specific strategies 247 for how to choose a block to use to satisfy a request. See also 248 :ref:`module-pw_allocator-design-block`. Derived types include: 249 250 - :ref:`module-pw_allocator-api-first_fit_allocator`: Chooses the first 251 block that's large enough to satisfy a request. This strategy is very fast, 252 but may increase fragmentation. 253 - :ref:`module-pw_allocator-api-best_fit_allocator`: Chooses the 254 smallest block that's large enough to satisfy a request. This strategy 255 maximizes the avilable space for large allocations, but may increase 256 fragmentation and is slower. 257 - :ref:`module-pw_allocator-api-worst_fit_allocator`: Chooses the 258 largest block if it's large enough to satisfy a request. This strategy 259 minimizes the amount of memory in unusably small blocks, but is slower. 260 - :ref:`module-pw_allocator-api-bucket_block_allocator`: Sorts and stores 261 each free blocks in a :ref:`module-pw_allocator-api-bucket` with a given 262 maximum block inner size. 263 264- :ref:`module-pw_allocator-api-typed_pool`: Efficiently creates and 265 destroys objects of a single given type. 266 267Forwarding allocator implementations 268==================================== 269This module provides several "forwarding" allocators, as described in 270:ref:`module-pw_allocator-design-forwarding`. The following is an overview. 271Consult the :ref:`module-pw_allocator-api` for additional details. 272 273- :ref:`module-pw_allocator-api-fallback_allocator`: Dispatches first to a 274 primary allocator, and, if that fails, to a secondary allocator. 275- :ref:`module-pw_allocator-api-pmr_allocator`: Adapts an allocator to be a 276 ``std::pmr::polymorphic_allocator``, which can be used with standard library 277 containers that `use allocators`_, such as ``std::pmr::vector<T>``. 278- :ref:`module-pw_allocator-api-synchronized_allocator`: Synchronizes access to 279 another allocator, allowing it to be used by multiple threads. 280- :ref:`module-pw_allocator-api-tracking_allocator`: Wraps another allocator and 281 records its usage. 282 283.. _module-pw_allocator-guide-custom_allocator: 284 285Custom allocator implementations 286================================ 287If none of the allocator implementations provided by this module meet your 288needs, you can implement your allocator and pass it into any routine that uses 289the generic interface. 290 291:ref:`module-pw_allocator-api-allocator` uses an `NVI`_ pattern. To add a custom 292allocator implementation, you must at a miniumum implement the ``DoAllocate`` 293and ``DoDeallocate`` methods. 294 295For example, the following is a forwarding allocator that simply writes to the 296log whenever a threshold is exceeded: 297 298.. literalinclude:: examples/custom_allocator.h 299 :language: cpp 300 :linenos: 301 :start-after: [pw_allocator-examples-custom_allocator] 302 303.. literalinclude:: examples/custom_allocator.cc 304 :language: cpp 305 :linenos: 306 :start-after: [pw_allocator-examples-custom_allocator] 307 308There are also several optional methods you can provide: 309 310- If an implementation of ``DoResize`` isn't provided, then ``Resize`` will 311 always return false. 312- If an implementation of ``DoReallocate`` isn't provided, then ``Reallocate`` 313 will try to ``Resize``, and, if unsuccessful, try to ``Allocate``, copy, and 314 ``Deallocate``. 315- If an implementation of ``DoGetInfo`` isn't provided, then ``GetInfo`` 316 will always return ``pw::Status::Unimplmented``. 317 318Custom allocators can indicate which optional methods they implement and what 319optional behaviors they want from the base class by specifying 320:ref:`module-pw_allocator-api-capabilities` when invoking the base class 321constructor. 322 323.. TODO: b/328076428 - Make Deallocate optional once traits supporting 324 MonotonicAllocator are added. 325 326-------------------- 327Measure memory usage 328-------------------- 329You can observe how much memory is being used for a particular use case using a 330:ref:`module-pw_allocator-api-tracking_allocator`. 331 332.. literalinclude:: examples/metrics.cc 333 :language: cpp 334 :linenos: 335 :start-after: [pw_allocator-examples-metrics-custom_metrics1] 336 :end-before: [pw_allocator-examples-metrics-custom_metrics1] 337 338.. literalinclude:: examples/metrics.cc 339 :language: cpp 340 :linenos: 341 :start-after: [pw_allocator-examples-metrics-custom_metrics2] 342 :end-before: [pw_allocator-examples-metrics-custom_metrics2] 343 344Metric data can be retrieved according to the steps described in 345:ref:`module-pw_metric-exporting`, or by using the ``Dump`` method of 346:ref:`module-pw_metric-group`: 347 348.. literalinclude:: examples/metrics.cc 349 :language: cpp 350 :linenos: 351 :start-after: [pw_allocator-examples-metrics-dump] 352 :end-before: [pw_allocator-examples-metrics-dump] 353 354 355The ``CustomMetrics`` type used in the example above is a struct provided by the 356developer. You can create your own metrics structs that enable zero or more of 357the following metrics: 358 359- **requested_bytes**: The number of bytes currently requested from this 360 allocator. 361- **peak_requested_bytes**: The most bytes requested from this allocator at any 362 one time. 363- **cumulative_requested_bytes**: The total number of bytes that have been 364 requested from this allocator across its lifetime. 365- **allocated_bytes**: The number of bytes currently allocated by this 366 allocator. 367- **peak_allocated_bytes**: The most bytes allocated by this allocator at any 368 one time. 369- **cumulative_allocated_bytes**: The total number of bytes that have been 370 allocated by this allocator across its lifetime. 371- **num_allocations**: The number of allocation requests this allocator has 372 successfully completed. 373- **num_deallocations**: The number of deallocation requests this allocator has 374 successfully completed. 375- **num_resizes**: The number of resize requests this allocator has successfully 376 completed. 377- **num_reallocations**: The number of reallocation requests this allocator has 378 successfully completed. 379- **num_failures**: The number of requests this allocator has failed to 380 complete. 381 382If you only want a subset of these metrics, you can implement your own metrics 383struct. For example: 384 385.. literalinclude:: examples/metrics.cc 386 :language: cpp 387 :linenos: 388 :start-after: [pw_allocator-examples-metrics-custom_metrics1] 389 :end-before: [pw_allocator-examples-metrics-custom_metrics1] 390 391If you have multiple routines that share an underlying allocator that you want 392to track separately, you can create multiple tracking allocators that forward to 393the same underlying allocator: 394 395.. literalinclude:: examples/metrics.cc 396 :language: cpp 397 :linenos: 398 :start-after: [pw_allocator-examples-metrics-multiple_trackers] 399 :end-before: [pw_allocator-examples-metrics-multiple_trackers] 400 401Measure fragmentation 402===================== 403 404If you are using a :ref:`module-pw_allocator-api-block_allocator`, you can use 405the ``MeasureFragmentation`` method to examine how fragmented the heap is. This 406method returns a :ref:`module-pw_allocator-api-fragmentation` struct, which 407includes the "sum of squares" and the sum of the inner sizes of the current free 408blocks. On a platform or host with floating point support, you can divide the 409square root of the sum of squares by the sum to obtain a number that ranges from 4100 to 1 to indicate maximal and minimal fragmenation, respectively. Subtracting 411this number from 1 can give a more intuitive "fragmenation score". 412 413For example, consider a heap consisting of the following blocks: 414 415- 100 bytes in use. 416- 200 bytes free. 417- 50 bytes in use. 418- 10 bytes free. 419- 200 bytes in use. 420- 300 bytes free. 421 422For such a heap, ``MeasureFragmentation`` will return 130100 and 510. The above 423calculation gives a fragmentation score of ``1 - sqrt(130100) / 510``, which is 424approximately ``0.29``. 425 426.. TODO: b/328648868 - Add guide for heap-viewer and link to cli.rst. 427 428------------------------ 429Detect memory corruption 430------------------------ 431The :ref:`module-pw_allocator-design-block` class provides a few different 432mechanisms to help detect memory corruptions when they happen. First, on every 433deallocation it will check the integrity of the block header and assert if it 434has been modified. 435 436Additionally, you can enable poisoning to detect additional memory corruptions 437such as use-after-frees. The :ref:`module-pw_allocator-module-configuration` for 438``pw_allocator`` includes the ``PW_ALLOCATOR_BLOCK_POISON_INTERVAL`` option, 439which will "poison" every N-th ``Block``. Allocators "poison" blocks on 440deallocation by writing a set pattern to the usable memory, and later check on 441allocation that the pattern is intact. If it's not, some routine has modified 442unallocated memory. 443 444---------------------- 445Test custom allocators 446---------------------- 447If you create your own allocator implementation, it's strongly recommended that 448you test it as well. If you're creating a forwarding allocator, you can use 449:ref:`module-pw_allocator-api-allocator_for_test`. This simple allocator 450provides its own backing storage and automatically frees any outstanding 451allocations when it goes out of scope. It also tracks the most recent values 452provided as parameters to the interface methods. 453 454For example, the following tests the custom allocator from 455:ref:`module-pw_allocator-guide-custom_allocator`: 456 457.. literalinclude:: examples/custom_allocator_test.cc 458 :language: cpp 459 :linenos: 460 :start-after: [pw_allocator-examples-custom_allocator-unit_test] 461 :end-before: [pw_allocator-examples-custom_allocator-unit_test] 462 463You can also extend the :ref:`module-pw_allocator-api-test_harness` to perform 464pseudorandom sequences of allocations and deallocations, e.g. as part of a 465performance test: 466 467.. literalinclude:: examples/custom_allocator_test_harness.h 468 :language: cpp 469 :linenos: 470 :start-after: [pw_allocator-examples-custom_allocator-test_harness] 471 472.. literalinclude:: examples/custom_allocator_perf_test.cc 473 :language: cpp 474 :linenos: 475 :start-after: [pw_allocator-examples-custom_allocator-perf_test] 476 477Even better, you can easily add fuzz tests for your allocator. This module 478uses the :ref:`module-pw_allocator-api-test_harness` to integrate with 479:ref:`module-pw_fuzzer` and provide 480:ref:`module-pw_allocator-api-fuzzing_support`. 481 482.. literalinclude:: examples/custom_allocator_test.cc 483 :language: cpp 484 :linenos: 485 :start-after: [pw_allocator-examples-custom_allocator-fuzz_test] 486 :end-before: [pw_allocator-examples-custom_allocator-fuzz_test] 487 488----------------------------- 489Measure custom allocator size 490----------------------------- 491If you create your own allocator implementation, you may wish to measure its 492code size, similar to measurements in the module's own 493:ref:`module-pw_allocator-size-reports`. You can use ``pw_bloat`` and 494:ref:`module-pw_allocator-api-size_reporter` to create size reports as described 495in :ref:`bloat-howto`. 496 497For example, the C++ code for a size report binary might look like: 498 499.. literalinclude:: examples/size_report.cc 500 :language: cpp 501 :linenos: 502 :start-after: [pw_allocator-examples-size_report] 503 504The resulting binary could be compared with the binary produced from 505pw_allocator/size_report/first_fit.cc to identify just the code added in this 506case by ``CustomAllocator``. 507 508For example, the GN build rule to generate a size report might look liek: 509 510.. code-block:: 511 512 pw_size_diff("size_report") { 513 title = "Example size report" 514 binaries = [ 515 { 516 target = ":size_report" 517 base = "$dir_pw_allocator/size_report:first_fit" 518 label = "CustomAllocator" 519 }, 520 ] 521 } 522 523The size report produced by this rule would render as: 524 525.. include:: examples/custom_allocator_size_report 526 527.. _AllocatorAwareContainers: https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer 528.. _NVI: https://en.wikipedia.org/wiki/Non-virtual_interface_pattern 529.. _RAII: https://en.cppreference.com/w/cpp/language/raii 530.. _repository: https://bazel.build/concepts/build-ref#repositories 531.. _use allocators: https://en.cppreference.com/w/cpp/memory/uses_allocator 532