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 struct lockfree_queue_element {
00170     struct lockfree_queue_element * volatile next;
00171     uintptr_t lock;
00172     void (*callback)(uint32_t);
00173     uint32_t parameter;
00174 };
00175 
00176 #include "atomic-queue/atomic-queue.h"
00177 
00178 #ifdef __cplusplus
00179 extern "C" {
00180 #endif
00181 
00182 typedef struct lockfree_queue_element arm_uc_callback_t;
00183 
00184 /**
00185  * @brief Add function to be executed to the queue.
00186  * @details The caller is responsible for managing the memory for each element
00187  *          in the queue, i.e., allocating enough struct lockfree_queue_element
00188  *          to hold the number of outstanding callbacks in the queue.
00189  *
00190  * @param storage Pointer to struct lockfree_queue_element.
00191  * @param callback Function pointer to function being scheduled to run later.
00192  * @param parameter uint32_t value to be passed as parameter to the callback function.
00193  * @return True when the callback was successfully scheduled.
00194  */
00195 bool ARM_UC_PostCallback(arm_uc_callback_t* storage, void (*callback)(uint32_t), uint32_t parameter);
00196 
00197 /**
00198  * @brief Calling this function processes all callbacks in the queue.
00199  */
00200 void ARM_UC_ProcessQueue(void);
00201 
00202 /**
00203  * @brief Calling this function processes a single callback in the queue.
00204  * @details The return value indicates whether there are more callbacks
00205  *          in the queue that needs handling.
00206  * @return True when there are more callbacks in the queue, false otherwise.
00207  */
00208 bool ARM_UC_ProcessSingleCallback(void);
00209 
00210 /**
00211  * @brief Register callback function for when callbacks are added to an empty queue.
00212  * @details This function is called at least once (maybe more) when callbacks are
00213  *          added to an empty queue. Useful for scheduling when the queue needs
00214  *          to be processed.
00215  * @param handler Function pointer to function to be called when elements are
00216  *        added to an empty queue.
00217  */
00218 void ARM_UC_AddNotificationHandler(void (*handler)(void));
00219 
00220 /**
00221  * @brief Initialize the scheduler.
00222  * @details This function primarily initializes the pool allocator for
00223  * callbacks. It should be called prior to using the scheduler at all.
00224  */
00225 void ARM_UC_SchedulerInit(void);
00226 
00227 /**
00228  * @brief Set the handler for scheduler errors.
00229  * @details This will be called in normal scheduler context when the pool runs
00230  * out of available callbacks.
00231  * 
00232  * @param[in] handler The function to call (thread context) when there is a
00233  *                    scheduler error.
00234  */
00235 void ARM_UC_SetSchedulerErrorHandler(void(*handler)(uint32_t));
00236 
00237 /**
00238  * @brief Get the maximum usage of the callback pool.
00239  * @details Uses the high watermark of the callback pool to indicate the 
00240  * worst-case callback usage.
00241  * 
00242  * @return the maximum number of callbacks that have been allocated from the
00243  * pool at one time.
00244  */
00245 uint32_t ARM_UC_SchedulerGetHighWatermark(void);
00246 
00247 /**
00248  * @brief Get the current number of queued callbacks
00249  * @details This is a function for running tests. The value returned by this
00250  * function cannot be relied upon in any system that is not exclusively
00251  * single-threaded, since any parallel thread or any interrupt could modify the
00252  * count.
00253  * 
00254  * @return The number of callbacks currently queued in the scheduler.
00255  */
00256 int32_t ARM_UC_SchedulerGetQueuedCount(void);
00257 
00258 #ifdef __cplusplus
00259 }
00260 #endif
00261 
00262 #endif // ARM_UPDATE_SCHEDULER_H