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