1 // Copyright 2016 The Fuchsia Authors 2 // Copyright (c) 2016, Google, Inc. All rights reserved 3 // 4 // Use of this source code is governed by a MIT-style 5 // license that can be found in the LICENSE file or at 6 // https://opensource.org/licenses/MIT 7 8 9 #pragma once 10 11 #include <err.h> 12 #include <kernel/mutex.h> 13 #include <list.h> 14 #include <zircon/types.h> 15 #include <sys/types.h> 16 17 __BEGIN_CDECLS 18 19 /** 20 * The pow2_range_allocator is a small utility library which partitions a set of 21 * ranges of integers into sub-ranges which are power of 2 in length and power 22 * of 2 aligned and then manages allocating and freeing the subranges for 23 * clients. It is responsible for breaking larger sub-regions into smaller ones 24 * as needed for allocation, and for merging sub-regions into larger sub-regions 25 * as needed during free operations. 26 * 27 * Its primary use is as a utility library for plaforms who need to manage 28 * allocating blocks MSI IRQ IDs on behalf of the PCI bus driver, but could (in 29 * theory) be used for other things). 30 */ 31 32 typedef struct p2ra_state { 33 mutex_t lock; 34 struct list_node ranges; 35 struct list_node unused_blocks; 36 struct list_node allocated_blocks; 37 struct list_node* free_block_buckets; 38 uint bucket_count; 39 } p2ra_state_t; 40 41 /** 42 * Initialize the state of a pow2 range allocator. 43 * 44 * @param state A pointer to the state structure to be initialized. 45 * @param max_alloc_size The maximum size of a single contiguous allocation. 46 * Must be a power of 2. 47 * 48 * @return A status code indicating the success or failure of the operation. 49 */ 50 zx_status_t p2ra_init(p2ra_state_t* state, uint max_alloc_size); 51 52 /** 53 * Free all of the state associated with a previously initialized pow2 range 54 * allocator. 55 * 56 * @param state A pointer to the state structure to be cleaned up. 57 */ 58 void p2ra_free(p2ra_state_t* state); 59 60 /** 61 * Add a range of uints to the pool of ranges to be allocated. 62 * 63 * @param state A pointer to the state structure to add the range to. 64 * @param range_start The start of the uint range. 65 * @param range_len The length of the uint range. 66 * 67 * @return A status code incidcating the success or failure of the operation. 68 * Possible return values include 69 * ++ ZX_ERR_INVALID_ARGS range_len is zero, or would cause the range to wrap the 70 * maximum range of a uint. 71 * ++ ZX_ERR_ALREADY_EXISTS the specified range overlaps with a range already added 72 * to the allocator. 73 * ++ ZX_ERR_NO_MEMORY Not enough memory to allocate the bookkeeping required for 74 * managing the range. 75 */ 76 zx_status_t p2ra_add_range(p2ra_state_t* state, uint range_start, uint range_len); 77 78 /** 79 * Attempt to allocate a range of uints from the available sub-ranges. The 80 * sizeo the allocated range must be a power of 2, and if the allocation 81 * succeeds, it is guaranteed to be aligned on a power of 2 boundary matching it 82 * size. 83 * 84 * @param state A pointer to the state structure to allocate from. 85 * @param size The requested size of the region. 86 * @param out_range_start An out parameter which will hold the start of the 87 * allocated range upon success. 88 * 89 * @return A status code indicating the success or failure of the operation. 90 * Possible return values include 91 * ++ ZX_ERR_INVALID_ARGS Multiple reasons, including... 92 * ++ size is zero. 93 * ++ size is not a power of two. 94 * ++ out_range_start is NULL. 95 * ++ ZX_ERR_NO_RESOURCES No contiguous, aligned region could be found to satisfy 96 * the allocation request. 97 * ++ ZX_ERR_NO_MEMORY A region could be found, but memory required for bookkeeping 98 * could not be allocated. 99 */ 100 zx_status_t p2ra_allocate_range(p2ra_state_t* state, uint size, uint* out_range_start); 101 102 /** 103 * Free a range previously allocated using p2ra_allocate_range. 104 * 105 * @param state A pointer to the state structure to return the range to. 106 * @param range_start The start of the previously allocated range. 107 * @param size The size of the previously allocated range. 108 */ 109 void p2ra_free_range(p2ra_state_t* state, uint range_start, uint size); 110 111 __END_CDECLS 112