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