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#include <lib/pow2_range_allocator.h> 9 10#include <assert.h> 11#include <debug.h> 12#include <fbl/auto_call.h> 13#include <fbl/auto_lock.h> 14#include <pow2.h> 15#include <stdlib.h> 16#include <string.h> 17#include <trace.h> 18 19#define LOCAL_TRACE 0 20 21typedef struct p2ra_block { 22 struct list_node node; 23 uint bucket; 24 uint start; 25} p2ra_block_t; 26 27typedef struct p2ra_range { 28 struct list_node node; 29 uint start, len; 30} p2ra_range_t; 31 32static inline p2ra_block_t* p2ra_get_unused_block(p2ra_state_t* state) { 33 DEBUG_ASSERT(state); 34 35 if (!list_is_empty(&state->unused_blocks)) 36 return list_remove_head_type(&state->unused_blocks, p2ra_block_t, node); 37 38 return (p2ra_block_t*)calloc(1, sizeof(p2ra_block_t)); 39} 40 41static inline void p2ra_free_block_list(struct list_node* block_list) { 42 p2ra_block_t* block; 43 while ((block = list_remove_head_type(block_list, p2ra_block_t, node)) != NULL) 44 free(block); 45} 46 47static inline void p2ra_free_range_list(struct list_node* range_list) { 48 p2ra_range_t* range; 49 while ((range = list_remove_head_type(range_list, p2ra_range_t, node)) != NULL) 50 free(range); 51} 52 53static void p2ra_return_free_block(p2ra_state_t* state, 54 p2ra_block_t* block, 55 bool merge_allowed) { 56 DEBUG_ASSERT(state); 57 DEBUG_ASSERT(block); 58 DEBUG_ASSERT(block->bucket < state->bucket_count); 59 DEBUG_ASSERT(!list_in_list(&block->node)); 60 DEBUG_ASSERT(!(block->start & ((1u << block->bucket) - 1))); 61 62 /* Return the block to its proper free bucket, sorted by base ID. Start by 63 * finding the block which should come after this block in the list. */ 64 struct list_node* l = &state->free_block_buckets[block->bucket]; 65 p2ra_block_t* after = list_peek_head_type(l, p2ra_block_t, node); 66 uint block_len = 1u << block->bucket; 67 68 while (after) { 69 /* We do not allow ranges to overlap */ 70 __UNUSED uint after_len = 1u << after->bucket; 71 DEBUG_ASSERT((block->start >= (after->start + after_len)) || 72 (after->start >= (block->start + block_len))); 73 74 if (after->start > block->start) { 75 list_add_before(&after->node, &block->node); 76 break; 77 } 78 79 /* Advance the iterator */ 80 after = list_next_type(l, &after->node, p2ra_block_t, node); 81 } 82 83 /* If no block comes after this one, it goes on the end of the list */ 84 if (!after) 85 list_add_tail(l, &block->node); 86 87 /* Don't merge blocks in the largest bucket. */ 88 if (block->bucket + 1 == state->bucket_count) 89 return; 90 91 /* Check to see if we should be merging this block into a larger aligned block. */ 92 p2ra_block_t* first; 93 p2ra_block_t* second; 94 if (block->start & ((block_len << 1) - 1)) { 95 /* Odd alignment. This might be the second block of a merge pair */ 96 second = block; 97 first = list_prev_type(l, &block->node, p2ra_block_t, node); 98 } else { 99 /* Even alignment. This might be the first block of a merge pair */ 100 first = block; 101 second = list_next_type(l, &block->node, p2ra_block_t, node); 102 } 103 104 /* Do these chunks fit together? */ 105 if (first && second) { 106 uint first_len = 1u << first->bucket; 107 if ((first->start + first_len) == second->start) { 108 /* Assert that we are allowed to perform a merge. If the caller is 109 * not expecting us to have to merge anything, then there is a fatal 110 * bookkeeping error somewhere */ 111 DEBUG_ASSERT(merge_allowed); 112 DEBUG_ASSERT(first->bucket == second->bucket); 113 114 /* Remove the two blocks' bookkeeping from their bucket */ 115 list_delete(&first->node); 116 list_delete(&second->node); 117 118 /* Place one half of the bookkeeping back on the unused list */ 119 list_add_tail(&state->unused_blocks, &second->node); 120 121 /* Reuse the other half to track the newly merged block, and place 122 * it in the next bucket size up. */ 123 first->bucket++; 124 p2ra_return_free_block(state, first, merge_allowed); 125 } 126 } 127} 128 129zx_status_t p2ra_init(p2ra_state_t* state, uint max_alloc_size) { 130 if (!state) 131 return ZX_ERR_INVALID_ARGS; 132 133 if (!max_alloc_size || !ispow2(max_alloc_size)) { 134 TRACEF("max_alloc_size (%u) is not an integer power of two!\n", max_alloc_size); 135 return ZX_ERR_INVALID_ARGS; 136 } 137 138 /* Allocate the storage for our free buckets */ 139 state->bucket_count = log2_uint_floor(max_alloc_size) + 1; 140 const size_t size = state->bucket_count * sizeof(state->free_block_buckets[0]); 141 state->free_block_buckets = static_cast<list_node*>(malloc(size)); 142 if (!state->free_block_buckets) { 143 TRACEF("Failed to allocate storage for %u free bucket lists!\n", state->bucket_count); 144 return ZX_ERR_NO_MEMORY; 145 } 146 147 /* Initialize the rest of our bookeeping */ 148 mutex_init(&state->lock); 149 list_initialize(&state->ranges); 150 list_initialize(&state->unused_blocks); 151 list_initialize(&state->allocated_blocks); 152 for (uint i = 0; i < state->bucket_count; ++i) 153 list_initialize(&state->free_block_buckets[i]); 154 155 return ZX_OK; 156} 157 158void p2ra_free(p2ra_state_t* state) { 159 DEBUG_ASSERT(state); 160 DEBUG_ASSERT(state->bucket_count); 161 DEBUG_ASSERT(state->free_block_buckets); 162 DEBUG_ASSERT(list_is_empty(&state->allocated_blocks)); 163 164 p2ra_free_range_list(&state->ranges); 165 p2ra_free_block_list(&state->unused_blocks); 166 p2ra_free_block_list(&state->allocated_blocks); 167 for (uint i = 0; i < state->bucket_count; ++i) 168 p2ra_free_block_list(&state->free_block_buckets[i]); 169 170 mutex_destroy(&state->lock); 171 memset(state, 0, sizeof(*state)); 172} 173 174zx_status_t p2ra_add_range(p2ra_state_t* state, uint range_start, uint range_len) { 175 LTRACEF("Adding range [%u, %u]\n", range_start, range_start + range_len - 1); 176 177 if (!state || 178 !range_len || 179 ((range_start + range_len) < range_start)) 180 return ZX_ERR_INVALID_ARGS; 181 182 zx_status_t ret = ZX_OK; 183 p2ra_range_t* new_range = NULL; 184 struct list_node new_blocks; 185 list_initialize(&new_blocks); 186 187 // if we're exiting with a failure, clean up anything we've allocated 188 auto ac = fbl::MakeAutoCall([&]() { 189 if (ret != ZX_OK) { 190 if (new_range) { 191 DEBUG_ASSERT(!list_in_list(&new_range->node)); 192 free(new_range); 193 } 194 195 p2ra_free_block_list(&new_blocks); 196 } 197 }); 198 199 /* Enter the lock and check for overlap with pre-existing ranges */ 200 fbl::AutoLock guard(&state->lock); 201 202 p2ra_range_t* range; 203 list_for_every_entry (&state->ranges, range, p2ra_range_t, node) { 204 if (((range->start >= range_start) && (range->start < (range_start + range_len))) || 205 ((range_start >= range->start) && (range_start < (range->start + range->len)))) { 206 TRACEF("Range [%u, %u] overlaps with existing range [%u, %u].\n", 207 range_start, range_start + range_len - 1, 208 range->start, range->start + range->len - 1); 209 ret = ZX_ERR_ALREADY_EXISTS; 210 return ret; 211 } 212 } 213 214 /* Allocate our range state */ 215 new_range = static_cast<p2ra_range_t*>(calloc(1, sizeof(*new_range))); 216 if (!new_range) { 217 ret = ZX_ERR_NO_MEMORY; 218 return ret; 219 } 220 new_range->start = range_start; 221 new_range->len = range_len; 222 223 /* Break the range we were given into power of two aligned chunks, and place 224 * them on the new blocks list to be added to the free-blocks buckets */ 225 DEBUG_ASSERT(state->bucket_count && state->free_block_buckets); 226 uint bucket = state->bucket_count - 1; 227 uint csize = (1u << bucket); 228 uint max_csize = csize; 229 while (range_len) { 230 /* Shrink the chunk size until it is aligned with the start of the 231 * range, and not larger than the number of irqs we have left. */ 232 bool shrunk = false; 233 while ((range_start & (csize - 1)) || (range_len < csize)) { 234 csize >>= 1; 235 bucket--; 236 shrunk = true; 237 } 238 239 /* If we didn't need to shrink the chunk size, perhaps we can grow it 240 * instead. */ 241 if (!shrunk) { 242 uint tmp = csize << 1; 243 while ((tmp <= max_csize) && 244 (tmp <= range_len) && 245 (!(range_start & (tmp - 1)))) { 246 bucket++; 247 csize = tmp; 248 tmp <<= 1; 249 DEBUG_ASSERT(bucket < state->bucket_count); 250 } 251 } 252 253 /* Break off a chunk of the range */ 254 DEBUG_ASSERT((1u << bucket) == csize); 255 DEBUG_ASSERT(bucket < state->bucket_count); 256 DEBUG_ASSERT(!(range_start & (csize - 1))); 257 DEBUG_ASSERT(csize <= range_len); 258 DEBUG_ASSERT(csize); 259 260 p2ra_block_t* block = p2ra_get_unused_block(state); 261 if (!block) { 262 TRACEF("WARNING! Failed to allocate block bookkeeping with sub-range " 263 "[%u, %u] still left to track.\n", 264 range_start, range_start + range_len - 1); 265 ret = ZX_ERR_NO_MEMORY; 266 return ret; 267 } 268 269 block->bucket = bucket; 270 block->start = range_start; 271 list_add_tail(&new_blocks, &block->node); 272 273 range_start += csize; 274 range_len -= csize; 275 } 276 277 /* Looks like we managed to allocate everything we needed to. Go ahead and 278 * add all of our newly allocated bookkeeping to the state. */ 279 list_add_tail(&state->ranges, &new_range->node); 280 281 p2ra_block_t* block; 282 while ((block = list_remove_head_type(&new_blocks, p2ra_block_t, node)) != NULL) 283 p2ra_return_free_block(state, block, false); 284 285 return ret; 286} 287 288zx_status_t p2ra_allocate_range(p2ra_state_t* state, uint size, uint* out_range_start) { 289 if (!state || !out_range_start) 290 return ZX_ERR_INVALID_ARGS; 291 292 if (!size || !ispow2(size)) { 293 TRACEF("Size (%u) is not an integer power of 2.\n", size); 294 return ZX_ERR_INVALID_ARGS; 295 } 296 297 uint orig_bucket = log2_uint_floor(size); 298 uint bucket = orig_bucket; 299 if (bucket >= state->bucket_count) { 300 TRACEF("Invalid size (%u). Valid sizes are integer powers of 2 from [1, %u]\n", 301 size, 1u << (state->bucket_count - 1)); 302 return ZX_ERR_INVALID_ARGS; 303 } 304 305 /* Lock state during allocation */ 306 p2ra_block_t* block = NULL; 307 308 fbl::AutoLock guard(&state->lock); 309 310 /* Find the smallest sized chunk which can hold the allocation and is 311 * compatible with the requested addressing capabilities */ 312 while (bucket < state->bucket_count) { 313 block = list_remove_head_type(&state->free_block_buckets[bucket], p2ra_block_t, node); 314 if (block) 315 break; 316 bucket++; 317 } 318 319 /* Nothing found, unlock and get out */ 320 if (!block) { 321 return ZX_ERR_NO_RESOURCES; 322 } 323 324 /* Looks like we have a chunk which can satisfy this allocation request. 325 * Split it as many times as needed to match the requested size. */ 326 DEBUG_ASSERT(block->bucket == bucket); 327 DEBUG_ASSERT(bucket >= orig_bucket); 328 329 while (bucket > orig_bucket) { 330 p2ra_block_t* split_block = p2ra_get_unused_block(state); 331 332 /* If we failed to allocate bookkeeping for the split block, put the block 333 * we failed to split back into the free list (merging if required), 334 * then fail the allocation */ 335 if (!split_block) { 336 TRACEF("Failed to allocated free bookkeeping block when attempting to " 337 "split for allocation\n"); 338 p2ra_return_free_block(state, block, true); 339 return ZX_ERR_NO_MEMORY; 340 } 341 342 DEBUG_ASSERT(bucket); 343 bucket--; 344 345 /* Cut the first chunk in half */ 346 block->bucket = bucket; 347 348 /* Fill out the bookkeeping for the second half of the chunk */ 349 split_block->start = block->start + (1u << block->bucket); 350 split_block->bucket = bucket; 351 352 /* Return the second half of the chunk to the free pool */ 353 p2ra_return_free_block(state, split_block, false); 354 } 355 356 /* Success! Mark the block as allocated and return the block to the user */ 357 list_add_head(&state->allocated_blocks, &block->node); 358 *out_range_start = block->start; 359 360 return ZX_OK; 361} 362 363void p2ra_free_range(p2ra_state_t* state, uint range_start, uint size) { 364 DEBUG_ASSERT(state); 365 DEBUG_ASSERT(size && ispow2(size)); 366 367 uint bucket = log2_uint_floor(size); 368 369 fbl::AutoLock guard(&state->lock); 370 371 /* In a debug build, find the specific block being returned in the list of 372 * allocated blocks and use it as the bookkeeping for returning to the free 373 * bucket. Because this is an O(n) operation, and serves only as a sanity 374 * check, we only do this in debug builds. In release builds, we just grab 375 * any piece of bookkeeping memory off the allocated_blocks list and use 376 * that instead. */ 377 p2ra_block_t* block; 378#if DEBUG_ASSERT_IMPLEMENTED 379 block = list_peek_head_type(&state->allocated_blocks, p2ra_block_t, node); 380 while (block) { 381 if ((block->start == range_start) && (block->bucket == bucket)) { 382 list_delete(&block->node); 383 break; 384 } 385 block = list_next_type(&state->allocated_blocks, &block->node, p2ra_block_t, node); 386 } 387 ASSERT(block); 388#else 389 block = list_remove_head_type(&state->allocated_blocks, p2ra_block_t, node); 390 ASSERT(block); 391 block->start = range_start; 392 block->bucket = bucket; 393#endif 394 395 /* Return the block to the free buckets (merging as needed) and we are done */ 396 p2ra_return_free_block(state, block, true); 397} 398