pw_allocator#

This module provides various building blocks for a dynamic allocator. This is composed of the following parts:

  • block: An implementation of a linked list of memory blocks, supporting splitting and merging of blocks.

  • freelist: A freelist, suitable for fast lookups of available memory chunks (i.e. block s).

Heap Integrity Check#

The Block class provides two check functions:

class Block#

The Block type is intended to be a building block component for allocators.

In this design, there is an explicit pointer to Next and Prev from the block header; the size is not encoded. The below diagram shows what this would look like for two blocks.

.------+---------------------------------.-----------------------------
|            Block A (first)             |       Block B (second)

+------+------+--------------------------+------+------+---------------
| Next | Prev |   usable space           | Next | Prev | usable space..
+------+------+--------------------------+------+--+---+---------------
^  |                                     ^         |
|  '-------------------------------------'         |
|                                                  |
'----------- Block B's prev points to Block A -----'

One use for these blocks is to use them as allocations, where each block represents an allocation handed out by malloc(). These blocks could also be used as part of a slab or buddy allocator.

Each block also contains flags for whether it is the last block (i.e. whether the Next pointer points to a valid block, or just denotes the end of this block), and whether the block is in use. These are encoded into the last two bits of the Next pointer, as follows:

.-----------------------------------------------------------------------.
|                            Block                                      |
+-----------------------------------------------------------------------+
|              Next            | Prev |         usable space            |
+----------------+------+------+      +                                 |
|   Ptr[N..2]    | Last | Used |      |                                 |
+----------------+------+------+------+---------------------------------+
^
|
'----------- Next() = Next & ~0x3 --------------------------------->

The first block in a chain is denoted by a nullptr Prev field, and the last block is denoted by the Last bit being set.

Note, this block class requires that the given block is aligned to an alignof(Block*) boundary. Because of this alignment requirement, each returned block will also be aligned to an alignof(Block*) boundary, and the size will always be rounded up to a multiple of alignof(Block*).

This class must be constructed using the static Init call.

Public Functions

inline size_t OuterSize() const#
Returns:

The total size of the block in bytes, including the header.

inline size_t InnerSize() const#
Returns:

The number of usable bytes inside the block.

inline std::byte *UsableSpace()#
Returns:

A pointer to the usable space inside this block.

Status Split(size_t head_block_inner_size, Block **new_block)#

Split this block, such that this block has an inner size of head_block_inner_size, and return a new block in the remainder of the space in new_block.

The remainder block will be aligned to an alignof(Block*) boundary (and head_block_inner_size will be rounded up). If the remaining space is not large enough to store a new Block after rounding, no splitting will occur.

Returns:

One of the the following:

  • OK: The split completed successfully.

  • INVALID_ARGUMENT: new_block is null.

  • FAILED_PRECONDITION: This block is in use and cannot be split.

  • OUT_OF_RANGE: The requested size for this block is greater than the current inner_size.

  • RESOURCE_EXHAUSTED: The split cannot occur because the remainder block would not be large enough to store a block header.

Status MergeNext()#

Merges this block with the one that comes after it.

return:

One of the following:

  • OK: The merge was successful.

  • OUT_OF_RANGE: Attempting to merge the last block failed.

  • FAILED_PRECONDITION: The blocks could not be merged because one of them was in use.

Pre:

The blocks must not be in use.

Status MergePrev()#

Merges this block with the one that comes before it.

return:

One of the following:

  • OK: The merge was successful.

  • OUT_OF_RANGE: Attempting to merge the first block failed.

  • FAILED_PRECONDITION: The blocks could not be merged because one of them was in use.

Warning

Merging with a previous block invalidates this block instance. Do not perform any operations on this instance after merging.

Pre:

The blocks must not be in use.

inline bool Used() const#

Indicates whether the block is in use.

Returns:

true if the block is in use or false if not.

inline bool Last() const#

Indicates whether this block is the last block or not (i.e. whether NextBlock() points to a valid block or not). This is needed because NextBlock() points to the end of this block, whether there is a valid block there or not.

Returns:

true is this is the last block or false if not.

inline void MarkUsed()#

Marks this block as in use.

inline void MarkFree()#

Marks this block as free.

inline void MarkLast()#

Marks this block as the last one in the chain.

inline void ClearLast()#

Clears the last bit from this block.

inline Block *Next() const#

Fetches the block immediately after this one.

Note

You should also check Last(). Next() may return a valid block, even if one does not exist.

inline Block *Prev() const#
Returns:

The block immediately before this one. Returns a null pointer if this is the first block.

inline bool IsValid() const#

Checks if a block is valid.

Returns:

false if a block is corrupted. Returns true if the following conditions are all true:

  • The block is aligned

  • The prev/next fields match with the previous and next blocks

  • The poisoned bytes are not damaged

void CrashIfInvalid()#

Crashes if a block is invalid. Uses PW_DCHECK to log information about why the block is invalid. Does nothing if the block is valid.

Public Static Functions

static Status Init(const span<std::byte> region, Block **block)#

Creates the first block for a given memory region.

return:

INVALID_ARGUMENT if the given region is unaligned to too small, or OK otherwise.

Pre:

The start of the given memory region must be aligned to an alignof(Block) boundary.

static inline Block *FromUsableSpace(std::byte *usable_space)#

Warning

This method does not do any checking; passing a random pointer will return a non-null pointer.

Returns:

A pointer to a Block, given a pointer to the start of the usable space inside the block. In other words, this operation is the opposite of UsableSpace(). In reality, this method just subtracts the appropriate amount from usable_space to point to the start of the owning block.

FreeList#

class FreeList#

Basic freelist implementation for an allocator. This implementation buckets by chunk size, with a list of user-provided buckets. Each bucket is a linked list of storage chunks. Because this freelist uses the added chunks themselves as list nodes, there is a lower bound of sizeof(FreeList.FreeListNode) bytes for chunks which can be added to this freelist. There is also an implicit bucket for “everything else”, for chunks which do not fit into a bucket.

Each added chunk will be added to the smallest bucket under which it fits. If it does not fit into any user-provided bucket, it will be added to the default bucket.

As an example, assume that the FreeList is configured with buckets of sizes {64, 128, 256, and 512} bytes. The internal state may look like the following:

bucket[0] (64B) --> chunk[12B] --> chunk[42B] --> chunk[64B] --> NULL
bucket[1] (128B) --> chunk[65B] --> chunk[72B] --> NULL
bucket[2] (256B) --> NULL
bucket[3] (512B) --> chunk[312B] --> chunk[512B] --> chunk[416B] --> NULL
bucket[4] (implicit) --> chunk[1024B] --> chunk[513B] --> NULL

Note that added chunks should be aligned to a 4-byte boundary.

This class is split into two parts:

  • FreeList implements all of the logic, and takes in pointers for two pw::Vector instances for its storage. This prevents us from having to specialise this class for every kMaxSize parameter for the vector.

  • FreeListBuffer then provides the storage for these two pw::Vector instances and instantiates FreeListInternal.

Subclassed by pw::allocator::FreeListBuffer< kNumBuckets >

Public Functions

Status AddChunk(span<std::byte> chunk)#

Adds a chunk to this freelist.

Returns:

  • OK - The chunk was added successfully.

  • OUT_OF_RANGE - The chunk could not be added for size reasons (e.g. the chunk is too small to store the FreeListNode).

span<std::byte> FindChunk(size_t size) const#

Finds an eligible chunk for an allocation of size size.

Note

This returns the first allocation possible within a given bucket; It does not currently optimize for finding the smallest chunk.

Returns:

  • On success - A span representing the chunk.

  • On failure (e.g. there were no chunks available for that allocation) - A span with a size of 0.

Status RemoveChunk(span<std::byte> chunk)#

Removes a chunk from this freelist.

Returns:

  • OK - The chunk was removed successfully.

  • NOT_FOUND - The chunk could not be found in this freelist.

Heap Poisoning#

Pigweed AI summary: The module disables heap poisoning by default due to the need for extra space, but users can enable it by using the build argument "pw_allocator_POISON_HEAP". When enabled, the allocator adds bytes before and after the usable space of each block and paints it with a randomized pattern. It checks if the pattern remains intact during each check and returns false if it is damaged.

By default, this module disables heap poisoning since it requires extra space. User can enable heap poisoning by enabling the pw_allocator_POISON_HEAP build arg.

$ gn args out
# Modify and save the args file to use heap poison.
pw_allocator_POISON_HEAP = true

When heap poisoning is enabled, pw_allocator will add sizeof(void*) bytes before and after the usable space of each Block, and paint the space with a hard-coded randomized pattern. During each check, pw_allocator will check if the painted space still remains the pattern, and return false if the pattern is damaged.

Heap Visualizer#

Pigweed AI summary: The Heap Visualizer is a tool provided by pw_allocator that allows users to visualize the state of the heap at the end of a dump file. The heap is represented by ASCII characters, with each character representing 4 bytes in the heap. The tool can be launched from a shell using the Pigweed environment, and requires arguments such as the path of the dump file and the start and end addresses of the heap. Options include enabling heap poisoning and specifying the size of a pointer. The tool and its

Functionality#

Pigweed AI summary: The pw_allocator provides a command called "pw heap-viewer" that helps visualize the state of the heap at the end of a dump file. The heap is represented by ASCII characters, with each character representing 4 bytes in the heap. An image is included to demonstrate this functionality.

pw_allocator supplies a pw command pw heap-viewer to help visualize the state of the heap at the end of a dump file. The heap is represented by ASCII characters, where each character represents 4 bytes in the heap.

../_images/pw_allocator_heap_visualizer_demo.png

Usage#

Pigweed AI summary: The heap visualizer can be launched from a shell using the Pigweed environment. The required arguments include the path of a file that contains malloc/free information, the start and end of the heap. Options include enabling heap poisoning and specifying the size of a pointer. The module and its documentation are currently incomplete and experimental.

The heap visualizer can be launched from a shell using the Pigweed environment.

$ pw heap-viewer --dump-file <directory of dump file> --heap-low-address
<hex address of heap lower address> --heap-high-address <hex address of heap
lower address> [options]

The required arguments are:

  • --dump-file is the path of a file that contains malloc/free information. Each line in the dump file represents a malloc/free call. malloc is represented as m <size> <memory address> and free is represented as f <memory address>. For example, a dump file should look like:

    m 20 0x20004450  # malloc 20 bytes, the pointer is 0x20004450
m 8 0x2000447c   # malloc 8 bytes, the pointer is 0x2000447c
f 0x2000447c     # free the pointer at 0x2000447c
...

    Any line not formatted as the above will be ignored.

  • --heap-low-address is the start of the heap. For example:

    --heap-low-address 0x20004440

  • --heap-high-address is the end of the heap. For example:

    --heap-high-address 0x20006040

Options include the following:

  • --poison-enable: If heap poisoning is enabled during the allocation or not. The value is False if the option is not specified and True otherwise.

  • --pointer-size <integer of pointer size>: The size of a pointer on the machine where malloc/free is called. The default value is 4.

Note, this module, and its documentation, is currently incomplete and experimental.