arm_uc_scheduler.h

00001 // ----------------------------------------------------------------------------
00002 // Copyright 2016-2017 ARM Ltd.
00003 //
00004 // SPDX-License-Identifier: Apache-2.0
00005 //
00006 // Licensed under the Apache License, Version 2.0 (the "License");
00007 // you may not use this file except in compliance with the License.
00008 // You may obtain a copy of the License at
00009 //
00010 //     http://www.apache.org/licenses/LICENSE-2.0
00011 //
00012 // Unless required by applicable law or agreed to in writing, software
00013 // distributed under the License is distributed on an "AS IS" BASIS,
00014 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00015 // See the License for the specific language governing permissions and
00016 // limitations under the License.
00017 // ----------------------------------------------------------------------------
00018 
00019 #ifndef ARM_UPDATE_SCHEDULER_H
00020 #define ARM_UPDATE_SCHEDULER_H
00021 
00022 #include <stddef.h>
00023 #include <stdint.h>
00024 #include <stdbool.h>
00025 
00026 /**
00027  * @file arm_uc_scheduler.h
00028  * @brief A simple, atomic event queue for embedded systems
00029  *
00030  * @details This is a simple scheduler useful for collecting events from
00031  * different threads and interrupt context so they can be executed from the
00032  * same thread/context.
00033  *
00034  * This can reduce the calldepth, ensure functions are executed from the same
00035  * thread, and provide a method for breaking out of interrupt context.
00036  *
00037  * Callbacks are executed FIFO.
00038  *
00039  * The notification handler should be used for processing the queue whenever it
00040  * is non-empty.
00041  *
00042  * This event queue uses an underlying atomic queue implementation
00043  * to provide atomicity guaranties without Critical Section primitives on
00044  * Cortex-M3 or later platforms. Linux and Cortex-M0 require a Critical Section
00045  * due to the lack of exclusive access primitives. See the atomic-queue
00046  * documentation for more detail on atomic access.
00047  *
00048  * An atomic queue has been used for three reasons:
00049  * 1. This allows the queue to be used in contexts where some RTOS primitives
00050  *    (mutexes) cannot be used, such as interrupt context.
00051  * 2. On many platforms, critical sections are very expensive, while atomics
00052  *    are not. Thus, there is a significant performance benefit to using atomic
00053  *    primitives wherever possible.
00054  * 3. Atomic operations have the least effect on all other execution contexts
00055  *    on the device. Critical sections have performance and responsiveness side
00056  *    effects. Mutexes can disrupt the execution of other threads. Atomics do
00057  *    not affect the execution of other contexts and are immune to priority
00058  *    inversion
00059  *
00060  * In short, the atomic queue is the most cooperative way of building an event
00061  * queue.
00062  *
00063  * This queue does, however have three major drawbacks:
00064  * 1. There is no way to directly cancel a callback. This is because the atomic
00065  *    queue has no way to remove an element from the middle of the queue. It
00066  *    can only be removed from the head of the queue.
00067  * 2. There is no way to prioritize one callback over another in the same
00068  *    queue. This is because there is no way to insert a callback into the
00069  *    middle of the queue. It can only be added at the end.
00070  * 3. The queue is entirely dependent on correct memory ownership, but it
00071  *    allocates no memory. The queue must own the callbacks while they are in
00072  *    the queue and any manipulation of that storage could break the behaviour
00073  *    of the queue.
00074  *
00075  * To compensate for 1., a callback author can provide a cancellation flag for
00076  * their callback that is checked on entry, but this may not know if it was
00077  * successful. The implementation of callback cancellation is beyond the scope
00078  * of this document.
00079  *
00080  * To compensate for 2., a prioritized event queue could be constructed from
00081  * two or more atomic queues. Since an event queue only takes a single pointer
00082  * of dedicated storage, this is can be used with a small number of priorities.
00083  * The implementation of a prioritized event queue is beyond the scope of this
00084  * document.
00085  *
00086  * In typical (non-atomic) structures, the solution for 3. is to allocate a
00087  * new callback storage block from the heap on each call. This would ensure
00088  * that the queue owns the block. However, this is not possible from an
00089  * interrupt context. Therefore, the queue uses a pool allocator instead.
00090  * However, pool allocators can run out of elements very easily. To ensure
00091  * that a particular callback can be scheduled, it is possible to give the
00092  * callback a statically allocated block instead. However, this introduces a
00093  * new failure mode: what happens if the block is already in use?
00094  *
00095  * To compensate for this failure mode, a per-element lock is provided in every
00096  * atomic queue element. The lock must be taken before ANY content of the
00097  * element is modified, including setting the callback and parameter. The lock
00098  * must only be released after the contents of the element have been copied
00099  * out.
00100  *
00101  * Because both statically allocated blocks and pool allocated blocks are
00102  * available, the user of the event queue is presented with a choice: Use a
00103  * statically allocated callback element, or use a pool allocated callback
00104  * element. Each option is better for different use-cases. When it is only
00105  * semantically possible for one callback from a given block of code to be in
00106  * flight at a time, it is more reliable for the callback to be statically
00107  * allocated. When it's possible for more than one callback from the same block
00108  * of code to be in flight at a time, then the pool allocator is a better
00109  * choice. Notwithstanding this distinction, if the scheduler fails to acquire
00110  * a lock on a statically allocated element, it will allocate a pool element
00111  * instead.
00112  *
00113  * To reduce API complexity, the callback queue mechanism works as below:
00114  *
00115  * When a callback is posted, the scheduler attempts to acquire the lock.
00116  * If either the callback storage is NULL or the lock cannot be acquired, the
00117  * scheduler pool-allocates a callback. If that fails, the scheduler uses a
00118  * dedicated error callback to notify the system that pool allocation has
00119  * failed, since this is a critical error.
00120  *
00121  * This event queue is composed of two major parts:
00122  * * The mechanism to post a callback (ARM_UC_PostCallback)
00123  * * The mechanism to process a callback
00124  *
00125  * When posting a callback, the scheduler first takes the lock on the supplied
00126  * callback structure, or pool-allocates a new one and then takes the lock. The
00127  * supplied event handler and event parameter are then placed into the supplied
00128  * (or pool-allocated) callback structure. The callback structure is then
00129  * placed in the event queue for later execution. If the queue was empty prior
00130  * to queuing this element, then the notification handler is invoked.
00131  *
00132  * **NOTE:** this means that the notification handler MUST be safe to execute
00133  * in IRQ context.
00134  *
00135  * When the queue is processed, callbacks are extracted in FIFO order. The
00136  * scheduler can be run in one of two modes:
00137  * * Consume the whole queue (ARM_UC_ProcessQueue)
00138  * * Consume single event (ARM_UC_ProcessSingleCallback)
00139  *
00140  * Both of these operations execute the same process:
00141  * 1. An element is dequeued from the atomic-queue
00142  * 2. The contents of the element are extracted
00143  * 3. The element is unlocked
00144  * 4. If the element was pool-allocated, it is freed
00145  * 5. The callback is executed with the supplied parameter
00146  *
00147  * Finally, ARM_UC_ProcessQueue goes back to 1, while
00148  * ARM_UC_ProcessSingleCallback returns true if there are still callbacks in
00149  * the queue, false otherwise.
00150  *
00151  * Callback Pool:
00152  * The callback pool is configured using a system define:
00153  *     ARM_UC_SCHEDULER_STORAGE_POOL_SIZE
00154  * To set the size of the pool, override this define in your build system. To
00155  * disable the pool, set this define to 0.
00156  *
00157  * To assist with callback pool debugging, an API is provided to calculate the
00158  * high watermark of the pool: ARM_UC_SchedulerGetHighWatermark(). This can be
00159  * compared to ARM_UC_SCHEDULER_STORAGE_POOL_SIZE to determine how many
00160  * elements were left at maximum usage.
00161  */
00162 
00163 /**
00164  * Use custom struct for the lockfree queue.
00165  * Struct contains function pointer callback and uint32_t parameter.
00166  */
00167 #define ATOMIC_QUEUE_CUSTOM_ELEMENT
00168 
00169 /* A queue element can store two different callback types: with and without context */
00170 typedef void (*arm_uc_no_context_callback_t)(uintptr_t);
00171 typedef void (*arm_uc_context_callback_t)(void *, uintptr_t);
00172 struct lockfree_queue_element {
00173     struct lockfree_queue_element *volatile next;
00174     uintptr_t lock;
00175     void *callback;
00176     uintptr_t parameter;
00177 };
00178 
00179 #include "atomic-queue/atomic-queue.h"
00180 
00181 #ifdef __cplusplus
00182 extern "C" {
00183 #endif
00184 
00185 typedef struct lockfree_queue_element arm_uc_callback_t;
00186 
00187 /**
00188  * @brief Add function to be executed to the queue.
00189  * @details The caller is responsible for managing the memory for each element
00190  *          in the queue, i.e., allocating enough struct lockfree_queue_element
00191  *          to hold the number of outstanding callbacks in the queue.
00192  *
00193  * @param storage Pointer to struct lockfree_queue_element.
00194  * @param callback Function pointer to function being scheduled to run later.
00195  * @param parameter uintptr_t value to be passed as parameter to the callback function.
00196  * @return True when the callback was successfully scheduled.
00197  */
00198 bool ARM_UC_PostCallback(arm_uc_callback_t *storage, arm_uc_no_context_callback_t callback, uintptr_t parameter);
00199 
00200 /**
00201  * @brief Add function to be executed to the queue and associate a context with it.
00202  * @details The caller is responsible for managing the memory for each element
00203  *          in the queue, i.e., allocating enough struct lockfree_queue_element
00204  *          to hold the number of outstanding callbacks in the queue.
00205  *
00206  * @param storage Pointer to struct lockfree_queue_element.
00207  * @param[in] ctx The callback context. If a context is not needed, use ATOMIC_QUEUE_NO_CONTEXT.
00208  *                If a context is needed, pass a non-NULL pointer.
00209  * @param callback Function pointer to function being scheduled to run later.
00210  * @param parameter uintptr_t value to be passed as parameter to the callback function.
00211  * @return True when the callback was successfully scheduled.
00212  */
00213 bool ARM_UC_PostCallbackCtx(arm_uc_callback_t *storage, void *ctx, arm_uc_context_callback_t callback, uintptr_t parameter);
00214 
00215 /**
00216  * @brief Schedule an error callback.
00217  * @details The error callback has priority over the other callbacks: as long as
00218  *          an error callback was posted using this function, it'll be dispatched before
00219  *          all the other callbacks in the queue. The storage for the error callback is
00220  *          internal to the scheduler. A single error callback can be scheduled at a time.
00221  *
00222  * @param[in] ctx The callback context. If a context is not needed, use ATOMIC_QUEUE_NO_CONTEXT.
00223  *                If a context is needed, pass a non-NULL pointer.
00224  * @param callback Function pointer to the error callback.
00225  * @param parameter uintptr_t value to be passed as parameter to the callback function.
00226  * @return True when the callback was successfully scheduled.
00227  */
00228 bool ARM_UC_PostErrorCallbackCtx(void *_ctx, arm_uc_context_callback_t _callback, uintptr_t _parameter);
00229 
00230 /**
00231  * @brief Calling this function processes all callbacks in the queue.
00232  */
00233 void ARM_UC_ProcessQueue(void);
00234 
00235 /**
00236  * @brief Calling this function processes a single callback in the queue.
00237  * @details The return value indicates whether there are more callbacks
00238  *          in the queue that needs handling.
00239  * @return True when there are more callbacks in the queue, false otherwise.
00240  */
00241 bool ARM_UC_ProcessSingleCallback(void);
00242 
00243 /**
00244  * @brief Register callback function for when callbacks are added to an empty queue.
00245  * @details This function is called at least once (maybe more) when callbacks are
00246  *          added to an empty queue. Useful for scheduling when the queue needs
00247  *          to be processed.
00248  * @param handler Function pointer to function to be called when elements are
00249  *        added to an empty queue.
00250  */
00251 void ARM_UC_AddNotificationHandler(void (*handler)(void));
00252 
00253 /**
00254  * @brief Initialize the scheduler.
00255  * @details This function primarily initializes the pool allocator for
00256  * callbacks. It should be called prior to using the scheduler at all.
00257  */
00258 void ARM_UC_SchedulerInit(void);
00259 
00260 /**
00261  * @brief Set the handler for scheduler errors.
00262  * @details This will be called in normal scheduler context when the pool runs
00263  * out of available callbacks.
00264  *
00265  * @param[in] handler The function to call (thread context) when there is a
00266  *                    scheduler error.
00267  */
00268 void ARM_UC_SetSchedulerErrorHandler(void(*handler)(uint32_t));
00269 
00270 /**
00271  * @brief Get the maximum usage of the callback pool.
00272  * @details Uses the high watermark of the callback pool to indicate the
00273  * worst-case callback usage.
00274  *
00275  * @return the maximum number of callbacks that have been allocated from the
00276  * pool at one time.
00277  */
00278 uint32_t ARM_UC_SchedulerGetHighWatermark(void);
00279 
00280 /**
00281  * @brief Get the current number of queued callbacks
00282  * @details This is a function for running tests. The value returned by this
00283  * function cannot be relied upon in any system that is not exclusively
00284  * single-threaded, since any parallel thread or any interrupt could modify the
00285  * count.
00286  *
00287  * @return The number of callbacks currently queued in the scheduler.
00288  */
00289 int32_t ARM_UC_SchedulerGetQueuedCount(void);
00290 
00291 #ifdef __cplusplus
00292 }
00293 #endif
00294 
00295 #endif // ARM_UPDATE_SCHEDULER_H