class RegionAllocator

Defined at line 137 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

RegionAllocator

== Overview ==

A RegionAllocator is a utility class designed to help with the bookkeeping

involved in managing the allocation/partitioning of a 64-bit space into

non-overlapping "Regions". In addition to the RegionAllocator, there are two

other classes involved in the use of a RegionAllcator;

RegionAllocator::Region and RegionAllocator::RegionPool.

A Region consists of an unsigned 64-bit base address and an unsigned 64-bit

size. A Region is considered valid iff its size is non-zero, and it does not

wrap its 64-bit space.

See the "Memory Allocation" section for a discussion of the RegionPool.

RegionAllocator users can create an allocator and then add any number of

non-overlapping Regions to its pool of regions available for allocation.

They may then request that regions be allocated from the pool either by

requesting that a region be allocated with a particular size/alignment, or

by asking for a specific base/size. The RegionAllocator will manage all of

the bookkeeping involved in breaking available regions into smaller chunks,

tracking allocated regions, and re-merging regions when they are returned to

the allocator.

== Memory Allocaion ==

RegionAllocators require dynamically allocated memory in order to store the

bookkeeping required for managing available regions. In order to control

heap fragmentation and the frequency of heap interaction, A RegionPool object

may be used to allocate bookkeeping overhead in larger slabs which are carved up

and placed on a free list to be used by a RegionAllocator. RegionPools are

created with a defined slab size as well as a maximum memory limit. The pool

will initially allocate a single slab, but will attempt to grow any time

bookkeeping is needed but the free list is empty and the allocation of

another slab would not push the allocator over its maximum memory limit.

RegionPools are ref-counted objects that may be shared by multiple

RegionAllocators. This allows sub-systems which use multiple allocators to

impose system-wide limits on bookkeeping overhead. If a RegionPool allocator

is to be used, it must be assigned to the RegionAllocator before any regions

can be added or allocated, and the pool may not be re-assigned while the

allocator is using any bookkeeping from the pool.

== APIs and Object lifecycle management ==

The API makes use of fbl managed pointer types in order to simplify lifecycle

management. RegionPools are managed with fbl::RefPtr while Regions are handed

out via std::unique_ptr. RegionAllocators themselves impose no lifecycle

restrictions and may be heap allocated, stack allocated, or embedded directly

in objects as the user sees fit. It is an error to allow a RegionAllocator

to destruct while there are allocations in flight.

== Dependencies ==

The RegionAllocator depends only on malloc/free and fbl. new/delete

implementations are provided internally, no global new/delete behavior needs

to be defined by the user.

== Thread Safety ==

RegionAllocator and RegionPools use fbl::Mutex objects to provide thread

safety in multi-threaded environments. As such, RegionAllocators are not

currently suitable for use in code which may run at IRQ context, or which

must never block.

Each RegionAllocator has its own mutex allowing for concurrent access across

multiple allocators, even when the allocators share the same RegionPool.

RegionPools also hold their own mutex which may be obtained by an Allocator

while holding the Allocator's Mutex.

== Simple Usage Example ==

/* Create a pool and assign it to a stack allocated allocator. Limit the

* bookkeeping memory to 32KB allocated from a single slab. This will ensure

* that no heap interactions take place after startup (during operation).

RegionAllocator alloc(

RegionAllocator::RegionPool::Create(32

10, 32

10));

/* Add regions to the pool which can be allocated from */

alloc.AddRegion({ .base = 0xC0000000, .size = 0x40000000 }); // [3GB, 4GB)

alloc.AddRegion({ .base = 0x4000000000, .size = 0x40000000 }); // [256GB, 257GB)

/* Grab some specific regions out of the available regions.

* Note: auto here will expand to RegionAllocator::Region::UPtr. Feel free

* to add your own using statement to lessen the C++ naming pain.

auto r1 = alloc.GetRegion({ 0xC0100000, 0x100000 }); // [3GB + 1MB, 3GB + 2MB)

auto r2 = alloc.GetRegion({ 0x4000100000, 0x100000 }); // [256GB + 1MB, 256GB + 2MB)

/* Grab some pointer aligned regions of various sizes */

auto r3 = alloc.GetRegion(1024);

auto r4 = alloc.GetRegion(75);

auto r5 = alloc.GetRegion(80000);

/* Grab some page aligned regions of various sizes */

auto r6 = alloc.GetRegion(1024, 4

10);

auto r7 = alloc.GetRegion(75, 4

10);

auto r8 = alloc.GetRegion(80000, 4

10);

/* Print some stuff about some of the allocations */

ZX_DEBUG_ASSERT(r3 != nullptr);

printf("R3 base %llx size %llx\n", r3->base, r3->size)

ZX_DEBUG_ASSERT(r8 != nullptr);

printf("R8 base %llx size %llx\n", r8->base, r8->size)

/* No need to clean up. Regions will automatically be returned to the

* allocator as they go out of scope. Then the allocator will return all of

* its available regions to the pool when it goes out of scope. Finally, the

* pool will free all of its memory as the allocator releases it reference

* to the pool.

Public Members

static const uint64_t kRegionPoolSlabSize

Public Methods

void ~RegionAllocator ()

Defined at line 30 of file ../../zircon/system/ulib/region-alloc/region-alloc.cc

zx_status_t SetRegionPool (const RegionPool::RefPtr & region_pool)

Set the RegionPool this RegionAllocator will obtain bookkeeping structures from.

Possible return values

++ ZX_ERR_BAD_STATE : The RegionAllocator already has bookkeeping

allocations. All allocated regions must be returned to the pool and the

pool Reset before the allocator may be changed.

Defined at line 58 of file ../../zircon/system/ulib/region-alloc/region-alloc.cc

void Reset ()

Reset allocator. Releases all available regions, but has no effect on

currently allocated regions.

Defined at line 45 of file ../../zircon/system/ulib/region-alloc/region-alloc.cc

zx_status_t AddRegion (const ralloc_region_t & region, AllowOverlap allow_overlap)

Add a region to the set of allocatable regions.

If allow_overlap is AllowOverlap::No, the added region may not overlap with

any previously added region and will be rejected if it does. If

allow_overlap is AllowOverlap::Yes, the added region will be union'ed with

existing available regions, provided it does not intersect any currently

allocated region.

Possible return values

++ ZX_ERR_NO_MEMORY : not enough bookkeeping memory available in our

assigned region pool to add the region.

++ ZX_ERR_INVALID_ARGS : One of the following conditions applies.

++++ The region is invalid (wraps the space, or size is zero)

++++ The region being added intersects one or more currently

allocated regions.

++++ The region being added intersects one ore more of the currently

available regions, and allow_overlap is false.

Defined at line 69 of file ../../zircon/system/ulib/region-alloc/region-alloc.cc

zx_status_t SubtractRegion (const ralloc_region_t & region, AllowIncomplete allow_incomplete)

Subtract a region from the set of allocatable regions.

If allow_incomplete is false, the subtracted region must exist entirely

within the set of available regions. If allow_incomplete is true, the

subtracted region will remove any portion of any available region it

intersects with.

Regardless of the value of the allow_incomplete flag, it is illegal to

attempt to subtract a region which intersects any currently allocated

region.

Possible return values

++ ZX_ERR_NO_MEMORY : not enough bookkeeping memory available in our

assigned region pool to subtract the region.

++ ZX_ERR_INVALID_ARGS : One of the following conditions applies.

++++ The region is invalid (wraps the space, or size is zero)

++++ The region being subtracted intersects one or more currently

allocated regions.

++++ The region being subtracted intersects portions of the space which

are absent from both the allocated and available sets, and

allow_incomplete is false.

Defined at line 100 of file ../../zircon/system/ulib/region-alloc/region-alloc.cc

void RegionAllocator ()

Defined at line 272 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

void RegionAllocator (const RegionPool::RefPtr & region_pool)

Defined at line 273 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

void RegionAllocator (RegionPool::RefPtr && region_pool)

Defined at line 274 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

void RegionAllocator (const RegionAllocator & c)

Defined at line 276 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

RegionAllocator & operator= (const RegionAllocator & c)

Defined at line 277 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

zx_status_t GetRegion (uint64_t size, uint64_t alignment, Region::UPtr & out_region)

Get a region out of the set of currently available regions which has a

specified size and alignment. Note; the alignment must be a power of

two. Pass 1 if alignment does not matter.

Possible return values

++ ZX_ERR_NO_MEMORY : not enough bookkeeping memory available in our

assigned region pool to perform the allocation.

++ ZX_ERR_INVALID_ARGS : size is zero, or alignment is not a power of two.

++ ZX_ERR_NOT_FOUND : No suitable region could be found in the set of

currently available regions which can satisfy the request.

Defined at line 282 of file ../../zircon/system/ulib/region-alloc/region-alloc.cc

zx_status_t GetRegion (uint64_t size, uint64_t alignment, Region::UPtr & out_region)

Get a region out of the set of currently available regions which has a

specified size and alignment. Note; the alignment must be a power of

two. Pass 1 if alignment does not matter.

Possible return values

++ ZX_ERR_NO_MEMORY : not enough bookkeeping memory available in our

assigned region pool to perform the allocation.

++ ZX_ERR_INVALID_ARGS : size is zero, or alignment is not a power of two.

++ ZX_ERR_NOT_FOUND : No suitable region could be found in the set of

currently available regions which can satisfy the request.

Defined at line 282 of file ../../zircon/system/ulib/region-alloc/region-alloc.cc

zx_status_t SetRegionPool (RegionPool::RefPtr && region_pool)

Defined at line 288 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

bool HasRegionPool ()

Defined at line 293 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

zx_status_t GetRegion (const ralloc_region_t & requested_region, Region::UPtr & out_region)

Get a region with a specific location and size out of the set of

currently available regions.

Possible return values

++ ZX_ERR_NO_MEMORY : not enough bookkeeping memory available in our

assigned region pool to perform the allocation.

++ ZX_ERR_INVALID_ARGS : The size of the requested region is zero.

++ ZX_ERR_NOT_FOUND : No suitable region could be found in the set of

currently available regions which can satisfy the request.

Defined at line 328 of file ../../zircon/system/ulib/region-alloc/region-alloc.cc

zx_status_t GetRegion (const ralloc_region_t & requested_region, Region::UPtr & out_region)

Get a region with a specific location and size out of the set of

currently available regions.

Possible return values

++ ZX_ERR_NO_MEMORY : not enough bookkeeping memory available in our

assigned region pool to perform the allocation.

++ ZX_ERR_INVALID_ARGS : The size of the requested region is zero.

++ ZX_ERR_NOT_FOUND : No suitable region could be found in the set of

currently available regions which can satisfy the request.

Defined at line 328 of file ../../zircon/system/ulib/region-alloc/region-alloc.cc

zx_status_t GetRegion (uint64_t size, Region::UPtr & out_region)

Helper which defaults the alignment of a size/alignment based allocation

to pointer-aligned.

Defined at line 374 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

zx_status_t GetRegion (uint64_t size, Region::UPtr & out_region)

Helper which defaults the alignment of a size/alignment based allocation

to pointer-aligned.

Defined at line 374 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

Region::UPtr GetRegion (uint64_t size, uint64_t alignment)

Helper versions of the GetRegion methods for those who don't care

about the specific reason for failure (nullptr will be returned on

failure).

Defined at line 381 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

Region::UPtr GetRegion (uint64_t size)

Defined at line 387 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

Region::UPtr GetRegion (const ralloc_region_t & requested_region)

Defined at line 393 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

bool TestRegionIntersects (const ralloc_region_t & region, TestRegionSet which)

Returns true if |region| intersects any of the regions in either the set of

currently allocated regions, or currently available regions.

region : The region to test

which : Either TestRegionSet::Allocated or TestRegionSet::Available to

test against the set of currently allocated or currently available

regions.

Defined at line 406 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

bool TestRegionContainedBy (const ralloc_region_t & region, TestRegionSet which)

Returns true if |region| is completely contained by any of the regions in

either the set of currently allocated regions, or currently available

regions.

region : The region to test

which : Either TestRegionSet::Allocated or TestRegionSet::Available to

test against the set of currently allocated or currently available

regions.

Defined at line 421 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

size_t AllocatedRegionCount ()

Defined at line 428 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

size_t AvailableRegionCount ()

Defined at line 433 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

template <typename WalkCallback>

void WalkAllocatedRegions (WalkCallback && cb)

Walk the allocated regions and call the user provided callback for each

entry. Stop when out of entries or the callback returns false.

*** It is absolutely required that the user callback not call into any other

RegionAllocator public APIs, and should likely not acquire any locks of any

kind. This method cannot protect against deadlocks and lock inversions that

are possible by acquiring the allocation lock before calling the user provided

callback.

Defined at line 447 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

template <typename WalkCallback>

void WalkAvailableRegions (WalkCallback && cb)

Walk the available regions and call the user provided callback for each

entry. Stop when out of entries or the callback returns false.

*** It is absolutely required that the user callback not call into any other

RegionAllocator public APIs, and should likely not acquire any locks of any

kind. This method cannot protect against deadlocks and lock inversions that

are possible by acquiring the allocation lock before calling the user provided

callback.

Defined at line 465 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

Enumerations

enum TestRegionSet

Name	Value
Allocated	0
Available	1

An enum which selects which set of regions to test against when testing for

intersection or containment. See TestRegionIntersect and

TestRegionContains for examples.

Defined at line 150 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

enum AllowOverlap

Name	Value
No	0
Yes	1

Enums which act as strongly typed bools and are used to control the

behavior of AddRegion and SubtractRegion.

Defined at line 157 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h

enum AllowIncomplete

Name	Value
No	0
Yes	1

Defined at line 162 of file ../../zircon/system/ulib/region-alloc/include/region-alloc/region-alloc.h