| // Copyright 2016 The Fuchsia Authors |
| // Copyright (c) 2016, Google, Inc. All rights reserved |
| // |
| // Use of this source code is governed by a MIT-style |
| // license that can be found in the LICENSE file or at |
| // https://opensource.org/licenses/MIT |
| |
| #ifndef ZIRCON_KERNEL_LIB_POW2_RANGE_ALLOCATOR_INCLUDE_LIB_POW2_RANGE_ALLOCATOR_H_ |
| #define ZIRCON_KERNEL_LIB_POW2_RANGE_ALLOCATOR_INCLUDE_LIB_POW2_RANGE_ALLOCATOR_H_ |
| |
| #include <sys/types.h> |
| #include <zircon/errors.h> |
| #include <zircon/types.h> |
| |
| #include <fbl/intrusive_double_list.h> |
| #include <kernel/mutex.h> |
| #include <ktl/unique_ptr.h> |
| |
| // Pow2RangeAllocator is a small utility class which partitions a set of |
| // ranges of integers into sub-ranges which are power of 2 in length and power |
| // of 2 aligned and then manages allocating and freeing the subranges for |
| // clients. It is responsible for breaking larger sub-regions into smaller ones |
| // as needed for allocation, and for merging sub-regions into larger sub-regions |
| // as needed during free operations. |
| // |
| // Its primary use is as a utility library for plaforms who need to manage |
| // allocating blocks MSI IRQ IDs on behalf of the PCI bus driver, but could (in |
| // theory) be used for other things). |
| |
| class Pow2RangeAllocator { |
| public: |
| constexpr Pow2RangeAllocator() = default; |
| |
| // Pow2RangeAllocators cannot be copied or moved. |
| Pow2RangeAllocator(const Pow2RangeAllocator&) = delete; |
| Pow2RangeAllocator(Pow2RangeAllocator&&) = delete; |
| Pow2RangeAllocator& operator=(const Pow2RangeAllocator&) = delete; |
| Pow2RangeAllocator& operator=(Pow2RangeAllocator&&) = delete; |
| |
| // Initialize the state of a pow2 range allocator. |
| // |
| // @param max_alloc_size The maximum size of a single contiguous allocation. |
| // Must be a power of 2. |
| // |
| // @return A status code indicating the success or failure of the operation. |
| zx_status_t Init(uint32_t max_alloc_size); |
| |
| // Free all of the state associated with a previously initialized pow2 range |
| // allocator. |
| void Free(); |
| |
| // Add a range of uint32_ts to the pool of ranges to be allocated. |
| // |
| // @param state A pointer to the state structure to add the range to. |
| // @param range_start The start of the uint32_t range. |
| // @param range_len The length of the uint32_t range. |
| // |
| // @return A status code incidcating the success or failure of the operation. |
| // Possible return values include |
| // ++ ZX_ERR_INVALID_ARGS range_len is zero, or would cause the range to wrap the |
| // maximum range of a uint32_t. |
| // ++ ZX_ERR_ALREADY_EXISTS the specified range overlaps with a range already added |
| // to the allocator. |
| // ++ ZX_ERR_NO_MEMORY Not enough memory to allocate the bookkeeping required for |
| // managing the range. |
| zx_status_t AddRange(uint32_t range_start, uint32_t range_len); |
| |
| // Attempt to allocate a range of uint32_ts from the available sub-ranges. The |
| // sizeo the allocated range must be a power of 2, and if the allocation |
| // succeeds, it is guaranteed to be aligned on a power of 2 boundary matching it |
| // size. |
| // |
| // @param size The requested size of the region. |
| // @param out_range_start An out parameter which will hold the start of the |
| // allocated range upon success. |
| // |
| // @return A status code indicating the success or failure of the operation. |
| // Possible return values include |
| // ++ ZX_ERR_INVALID_ARGS Multiple reasons, including... |
| // ++ size is zero. |
| // ++ size is not a power of two. |
| // ++ out_range_start is NULL. |
| // ++ ZX_ERR_NO_RESOURCES No contiguous, aligned region could be found to satisfy |
| // the allocation request. |
| // ++ ZX_ERR_NO_MEMORY A region could be found, but memory required for bookkeeping |
| // could not be allocated. |
| zx_status_t AllocateRange(uint32_t size, uint32_t* out_range_start); |
| |
| // Free a range previously allocated using AllocateRange. |
| // |
| // @param range_start The start of the previously allocated range. |
| // @param size The size of the previously allocated range. |
| void FreeRange(uint32_t range_start, uint32_t size); |
| |
| private: |
| struct Block : fbl::DoublyLinkedListable<ktl::unique_ptr<Block>> { |
| uint32_t bucket = 0u; |
| uint32_t start = 0u; |
| }; |
| using BlockList = fbl::DoublyLinkedList<ktl::unique_ptr<Block>>; |
| |
| struct Range : fbl::DoublyLinkedListable<ktl::unique_ptr<Range>> { |
| uint32_t start = 0u; |
| uint32_t len = 0u; |
| }; |
| using RangeList = fbl::DoublyLinkedList<ktl::unique_ptr<Range>>; |
| |
| ktl::unique_ptr<Block> GetUnusedBlock(); |
| void ReturnFreeBlock(ktl::unique_ptr<Block> block); |
| |
| DECLARE_MUTEX(Pow2RangeAllocator) lock_; |
| RangeList ranges_; |
| BlockList unused_blocks_; |
| BlockList allocated_blocks_; |
| ktl::unique_ptr<BlockList[]> free_block_buckets_; |
| uint32_t bucket_count_ = 0; |
| }; |
| |
| #endif // ZIRCON_KERNEL_LIB_POW2_RANGE_ALLOCATOR_INCLUDE_LIB_POW2_RANGE_ALLOCATOR_H_ |