pool_queue_exports.h

00001 /*
00002  * Copyright (c) 2016, ARM Limited, All Rights Reserved
00003  * SPDX-License-Identifier: Apache-2.0
00004  *
00005  * Licensed under the Apache License, Version 2.0 (the "License"); you may
00006  * not use this file except in compliance with the License.
00007  * You may obtain a copy of the License at
00008  *
00009  * http://www.apache.org/licenses/LICENSE-2.0
00010  *
00011  * Unless required by applicable law or agreed to in writing, software
00012  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
00013  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  * See the License for the specific language governing permissions and
00015  * limitations under the License.
00016  */
00017 #ifndef UVISOR_POOL_QUEUE_EXPORTS_H
00018 #define UVISOR_POOL_QUEUE_EXPORTS_H
00019 
00020 #include "api/inc/magic_exports.h"
00021 #include "api/inc/uvisor_exports.h"
00022 #include "api/inc/uvisor_semaphore_exports.h"
00023 #include "api/inc/uvisor_spinlock_exports.h"
00024 #include <stdint.h>
00025 #include <stddef.h>
00026 
00027 #define UVISOR_POOL_QUEUE_NON_BLOCKING (0)
00028 #define UVISOR_POOL_QUEUE_BLOCKING (1)
00029 
00030 #define UVISOR_POOL_SLOT_INVALID     ((uint8_t) 0xFFU)
00031 #define UVISOR_POOL_SLOT_IS_DEQUEUED ((uint8_t) 0xFEU)
00032 #define UVISOR_POOL_SLOT_IS_FREE     ((uint8_t) 0xFDU)
00033 #define UVISOR_POOL_MAX_VALID        ((uint8_t) 0xFCU)
00034 
00035 typedef uint8_t uvisor_pool_slot_t;
00036 
00037 typedef struct uvisor_pool_queue_entry {
00038     union {
00039         struct {
00040             /* The next slot in the queue */
00041             uvisor_pool_slot_t next;
00042 
00043             /* The previous slot in the queue */
00044             uvisor_pool_slot_t prev;
00045         } queued;
00046         struct {
00047             /* If the slot is free, the next available slot in the free list */
00048             uvisor_pool_slot_t next;
00049 
00050             /* If the slot is free or dequeued */
00051             uvisor_pool_slot_t state;
00052         } dequeued;
00053     };
00054 } uvisor_pool_queue_entry_t;
00055 
00056 /* These are assumed to only be statically allocated, so the management array
00057  * in in-place. */
00058 typedef struct uvisor_pool {
00059     /* Magic that identifies this as a uvisor_pool type. */
00060     uint32_t magic;
00061 
00062     /* The array holds slots of data. */
00063     void const * array;
00064 
00065     /* The distance between elements in the array. */
00066     size_t stride;
00067 
00068     /* The maximum number of elements that could be in the array. */
00069     uvisor_pool_slot_t num;
00070 
00071     /* Whether or not the queue can block callers who want to allocate slots
00072      * from the pool. If non-zero, when no slots is available in the pool,
00073      * callers will be blocked up to their timeout amount of time before giving
00074      * up. */
00075     int blocking;
00076 
00077     /* The number of items currently allocated from the pool. For testing and
00078      * debug purposes only. */
00079     uvisor_pool_slot_t num_allocated;
00080 
00081     /* The first free slot. */
00082     uvisor_pool_slot_t first_free;
00083 
00084     /* The semaphore is used to block allocations when the pool is full. */
00085     UvisorSemaphore semaphore;
00086 
00087     /* The spinlock serializes updates to the management array. */
00088     UvisorSpinlock spinlock;
00089 
00090     /* This must be at the end so we can allocate memory for pools by
00091      * allocating enough room for the size of the pool appended by an array of
00092      * entries. */
00093     uvisor_pool_queue_entry_t management_array[];
00094 } uvisor_pool_t;
00095 
00096 typedef struct uvisor_pool_queue {
00097     /* Magic that identifies this as a uvisor_pool_queue type. */
00098     uint32_t magic;
00099 
00100     /* The first allocated slot */
00101     uvisor_pool_slot_t head;
00102 
00103     /* The last allocated slot */
00104     uvisor_pool_slot_t tail;
00105 
00106     uvisor_pool_t * pool;
00107 } uvisor_pool_queue_t;
00108 
00109 /* Intialize a pool.
00110  * Return 0 on success, non-zero otherwise. */
00111 UVISOR_EXTERN int uvisor_pool_init(uvisor_pool_t * pool, void * array, size_t stride, size_t num, int blocking);
00112 
00113 /* Initialize a pool queue.
00114  * Return 0 on success, non-zero otherwise. */
00115 UVISOR_EXTERN int uvisor_pool_queue_init(uvisor_pool_queue_t * pool_queue, uvisor_pool_t * pool, void * array, size_t stride, size_t num, int blocking);
00116 
00117 /* Allocate a slot from the pool. If the pool has no more slots available,
00118  * block up to the specified length of time in milliseconds. No blocking will
00119  * occur if the timeout is zero or the pool was initialized as non-blocking.
00120  * This doesn't put anything in the slot for you. It's up to you to do that.
00121  * Return the index of the allocated slot, or UVISOR_POOL_SLOT_INVALID if
00122  * timed out waiting for an available slot. This function will spin until the
00123  * spin lock serializing access to the pool can be taken. */
00124 UVISOR_EXTERN uvisor_pool_slot_t uvisor_pool_allocate(uvisor_pool_t * pool, uint32_t timeout_ms);
00125 /* Attempt to allocate a slot. This function will fail if the spin lock
00126  * serializing access to the pool can not be taken. */
00127 UVISOR_EXTERN uvisor_pool_slot_t uvisor_pool_try_allocate(uvisor_pool_t * pool);
00128 
00129 /* Enqueue the specified slot into the queue. */
00130 UVISOR_EXTERN void uvisor_pool_queue_enqueue(uvisor_pool_queue_t * pool_queue, uvisor_pool_slot_t slot);
00131 UVISOR_EXTERN int uvisor_pool_queue_try_enqueue(uvisor_pool_queue_t * pool_queue, uvisor_pool_slot_t slot);
00132 
00133 /* Free the specified slot back into the pool. Invalid slots are ignored.
00134  * Return the slot that was freed, or UVISOR_POOL_SLOT_IS_FREE if the slot was
00135  * already freed, or UVISOR_POOL_SLOT_INVALID if the slot being requested to
00136  * free is outside the range of the queue. */
00137 UVISOR_EXTERN uvisor_pool_slot_t uvisor_pool_free(uvisor_pool_t * pool, uvisor_pool_slot_t slot);
00138 UVISOR_EXTERN uvisor_pool_slot_t uvisor_pool_try_free(uvisor_pool_t * pool, uvisor_pool_slot_t slot);
00139 
00140 /* Remove the specified slot from the queue. This function does not free the
00141  * specified slot back into the pool. Return the slot that was dequeued, or
00142  * UVISOR_POOL_SLOT_IS_DEQUEUED if the slot was already dequeued, or
00143  * UVISOR_POOL_SLOT_INVALID if the slot being requested to dequeue is outside
00144  * the range of the queue. */
00145 UVISOR_EXTERN uvisor_pool_slot_t uvisor_pool_queue_dequeue(uvisor_pool_queue_t * pool_queue, uvisor_pool_slot_t slot);
00146 
00147 /* Remove the first slot from the queue. This function does not free the
00148  * specified slot back into the pool. Return the slot that was dequeued or
00149  * UVISOR_POOL_SLOT_INVALID if the slot being requested to dequeue is outside
00150  * the range of the queue. */
00151 UVISOR_EXTERN uvisor_pool_slot_t uvisor_pool_queue_dequeue_first(uvisor_pool_queue_t * pool_queue);
00152 UVISOR_EXTERN uvisor_pool_slot_t uvisor_pool_queue_try_dequeue_first(uvisor_pool_queue_t * pool_queue);
00153 
00154 /* Find the first (in queue order) slot that the supplied query function
00155  * returns non-zero for. The query function is provided with `context` on every
00156  * invocation. This allows query functions to access additional data without
00157  * having to use global variables. `uvisor_pool_queue_find_first` is reentrant. */
00158 typedef int (*TQueryFN_Ptr)(uvisor_pool_slot_t slot, void * context);
00159 UVISOR_EXTERN uvisor_pool_slot_t uvisor_pool_queue_find_first(uvisor_pool_queue_t * pool_queue,
00160                                                               TQueryFN_Ptr query_fn, void * context);
00161 
00162 /* Inline helper function to make allocating slots for pool queues easier and
00163  * better encapsulated (clients don't need to pull the pool out of the pool
00164  * queue, or even realize pool_queue is implemented with a pool) */
00165 static inline uvisor_pool_slot_t uvisor_pool_queue_allocate(uvisor_pool_queue_t * pool_queue, uint32_t timeout_ms)
00166 {
00167     return uvisor_pool_allocate(pool_queue->pool, timeout_ms);
00168 }
00169 
00170 static inline uvisor_pool_slot_t uvisor_pool_queue_try_allocate(uvisor_pool_queue_t * pool_queue)
00171 {
00172     return uvisor_pool_try_allocate(pool_queue->pool);
00173 }
00174 
00175 /* Inline helper function to make freeing slots for pool queues easier and
00176  * better encapsulated (clients don't need to pull the pool out of the pool
00177  * queue, or even realize pool_queue is implemented with a pool) */
00178 static inline uvisor_pool_slot_t uvisor_pool_queue_free(uvisor_pool_queue_t * pool_queue, uvisor_pool_slot_t slot)
00179 {
00180     return uvisor_pool_free(pool_queue->pool, slot);
00181 }
00182 
00183 static inline uvisor_pool_slot_t uvisor_pool_queue_try_free(uvisor_pool_queue_t * pool_queue, uvisor_pool_slot_t slot)
00184 {
00185     return uvisor_pool_try_free(pool_queue->pool, slot);
00186 }
00187 
00188 /* Return a pointer to the specified slot within the pool. */
00189 static inline void * uvisor_pool_pointer_to(uvisor_pool_t * pool, uvisor_pool_slot_t slot)
00190 {
00191     if (slot >= pool->num) {
00192         return NULL;
00193     }
00194     return (uint8_t *) pool->array + pool->stride * slot;
00195 }
00196 
00197 typedef struct {
00198     int (*init)(uvisor_pool_t *, void *, size_t, size_t, int);
00199     int (*queue_init)(uvisor_pool_queue_t *, uvisor_pool_t *, void *, size_t, size_t, int);
00200     uvisor_pool_slot_t (*allocate)(uvisor_pool_t *, uint32_t);
00201     void (*queue_enqueue)(uvisor_pool_queue_t *, uvisor_pool_slot_t);
00202     uvisor_pool_slot_t (*free)(uvisor_pool_t *, uvisor_pool_slot_t);
00203     uvisor_pool_slot_t (*queue_dequeue)(uvisor_pool_queue_t *, uvisor_pool_slot_t);
00204     uvisor_pool_slot_t (*queue_dequeue_first)(uvisor_pool_queue_t *);
00205     uvisor_pool_slot_t (*queue_find_first)(uvisor_pool_queue_t *, TQueryFN_Ptr, void *);
00206 } UvisorPoolTable;
00207 
00208 #endif