MicroBitFiber.cpp

00001 /*
00002 The MIT License (MIT)
00003 
00004 Copyright (c) 2016 British Broadcasting Corporation.
00005 This software is provided by Lancaster University by arrangement with the BBC.
00006 
00007 Permission is hereby granted, free of charge, to any person obtaining a
00008 copy of this software and associated documentation files (the "Software"),
00009 to deal in the Software without restriction, including without limitation
00010 the rights to use, copy, modify, merge, publish, distribute, sublicense,
00011 and/or sell copies of the Software, and to permit persons to whom the
00012 Software is furnished to do so, subject to the following conditions:
00013 
00014 The above copyright notice and this permission notice shall be included in
00015 all copies or substantial portions of the Software.
00016 
00017 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00018 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00019 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
00020 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00021 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
00022 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
00023 DEALINGS IN THE SOFTWARE.
00024 */
00025 
00026 /**
00027   * Functionality definitions for the MicroBit Fiber scheduler.
00028   *
00029   * This lightweight, non-preemptive scheduler provides a simple threading mechanism for two main purposes:
00030   *
00031   * 1) To provide a clean abstraction for application languages to use when building async behaviour (callbacks).
00032   * 2) To provide ISR decoupling for EventModel events generated in an ISR context.
00033   */
00034 #include "MicroBitConfig.h"
00035 #include "MicroBitFiber.h"
00036 #include "MicroBitSystemTimer.h"
00037 
00038 /*
00039  * Statically allocated values used to create and destroy Fibers.
00040  * required to be defined here to allow persistence during context switches.
00041  */
00042 Fiber *currentFiber = NULL;                        // The context in which the current fiber is executing.
00043 static Fiber *forkedFiber = NULL;                  // The context in which a newly created child fiber is executing.
00044 static Fiber *idleFiber = NULL;                    // the idle task - performs a power efficient sleep, and system maintenance tasks.
00045 
00046 /*
00047  * Scheduler state.
00048  */
00049 static Fiber *runQueue = NULL;                     // The list of runnable fibers.
00050 static Fiber *sleepQueue = NULL;                   // The list of blocked fibers waiting on a fiber_sleep() operation.
00051 static Fiber *waitQueue = NULL;                    // The list of blocked fibers waiting on an event.
00052 static Fiber *fiberPool = NULL;                    // Pool of unused fibers, just waiting for a job to do.
00053 
00054 /*
00055  * Scheduler wide flags
00056  */
00057 static uint8_t fiber_flags = 0;
00058 
00059 
00060 /*
00061  * Fibers may perform wait/notify semantics on events. If set, these operations will be permitted on this EventModel.
00062  */
00063 static EventModel *messageBus = NULL;
00064 
00065 // Array of components which are iterated during idle thread execution, isIdleCallbackNeeded is polled during a systemTick.
00066 static MicroBitComponent* idleThreadComponents[MICROBIT_IDLE_COMPONENTS];
00067 
00068 /**
00069   * Utility function to add the currenty running fiber to the given queue.
00070   *
00071   * Perform a simple add at the head, to avoid complexity,
00072   *
00073   * Queues are normally very short, so maintaining a doubly linked, sorted list typically outweighs the cost of
00074   * brute force searching.
00075   *
00076   * @param f The fiber to add to the queue
00077   *
00078   * @param queue The run queue to add the fiber to.
00079   */
00080 void queue_fiber(Fiber *f, Fiber **queue)
00081 {
00082     __disable_irq();
00083 
00084     // Record which queue this fiber is on.
00085     f->queue = queue;
00086 
00087     // Add the fiber to the tail of the queue. Although this involves scanning the
00088     // list, it results in fairer scheduling.
00089     if (*queue == NULL)
00090     {
00091         f->next = NULL;
00092         f->prev = NULL;
00093         *queue = f;
00094     }
00095     else
00096     {
00097         // Scan to the end of the queue.
00098         // We don't maintain a tail pointer to save RAM (queues are nrmally very short).
00099         Fiber *last = *queue;
00100 
00101         while (last->next != NULL)
00102             last = last->next;
00103 
00104         last->next = f;
00105         f->prev = last;
00106         f->next = NULL;
00107     }
00108 
00109     __enable_irq();
00110 }
00111 
00112 /**
00113   * Utility function to the given fiber from whichever queue it is currently stored on.
00114   *
00115   * @param f the fiber to remove.
00116   */
00117 void dequeue_fiber(Fiber *f)
00118 {
00119     // If this fiber is already dequeued, nothing the there's nothing to do.
00120     if (f->queue == NULL)
00121         return;
00122 
00123     // Remove this fiber fromm whichever queue it is on.
00124     __disable_irq();
00125 
00126     if (f->prev != NULL)
00127         f->prev->next = f->next;
00128     else
00129         *(f->queue) = f->next;
00130 
00131     if(f->next)
00132         f->next->prev = f->prev;
00133 
00134     f->next = NULL;
00135     f->prev = NULL;
00136     f->queue = NULL;
00137 
00138     __enable_irq();
00139 
00140 }
00141 
00142 /**
00143   * Allocates a fiber from the fiber pool if availiable. Otherwise, allocates a new one from the heap.
00144   */
00145 Fiber *getFiberContext()
00146 {
00147     Fiber *f;
00148 
00149     __disable_irq();
00150 
00151     if (fiberPool != NULL)
00152     {
00153         f = fiberPool;
00154         dequeue_fiber(f);
00155         // dequeue_fiber() exits with irqs enabled, so no need to do this again!
00156     }
00157     else
00158     {
00159         __enable_irq();
00160 
00161         f = new Fiber();
00162 
00163         if (f == NULL)
00164             return NULL;
00165 
00166         f->stack_bottom = 0;
00167         f->stack_top = 0;
00168     }
00169 
00170     // Ensure this fiber is in suitable state for reuse.
00171     f->flags = 0;
00172     f->tcb.stack_base = CORTEX_M0_STACK_BASE;
00173 
00174     return f;
00175 }
00176 
00177 
00178 /**
00179   * Initialises the Fiber scheduler.
00180   * Creates a Fiber context around the calling thread, and adds it to the run queue as the current thread.
00181   *
00182   * This function must be called once only from the main thread, and before any other Fiber operation.
00183   *
00184   * @param _messageBus An event model, used to direct the priorities of the scheduler.
00185   */
00186 void scheduler_init(EventModel &_messageBus)
00187 {
00188     // If we're already initialised, then nothing to do.
00189     if (fiber_scheduler_running())
00190         return;
00191 
00192     // Store a reference to the messageBus provided.
00193     // This parameter will be NULL if we're being run without a message bus.
00194     messageBus = &_messageBus;
00195 
00196     // Create a new fiber context
00197     currentFiber = getFiberContext();
00198 
00199     // Add ourselves to the run queue.
00200     queue_fiber(currentFiber, &runQueue);
00201 
00202     // Create the IDLE fiber.
00203     // Configure the fiber to directly enter the idle task.
00204     idleFiber = getFiberContext();
00205     idleFiber->tcb.SP = CORTEX_M0_STACK_BASE - 0x04;
00206     idleFiber->tcb.LR = (uint32_t) &idle_task;
00207 
00208     if (messageBus)
00209     {
00210         // Register to receive events in the NOTIFY channel - this is used to implement wait-notify semantics
00211         messageBus->listen(MICROBIT_ID_NOTIFY, MICROBIT_EVT_ANY, scheduler_event, MESSAGE_BUS_LISTENER_IMMEDIATE);
00212         messageBus->listen(MICROBIT_ID_NOTIFY_ONE, MICROBIT_EVT_ANY, scheduler_event, MESSAGE_BUS_LISTENER_IMMEDIATE);
00213     }
00214 
00215     // register a period callback to drive the scheduler and any other registered components.
00216     new MicroBitSystemTimerCallback(scheduler_tick);
00217 
00218     fiber_flags |= MICROBIT_SCHEDULER_RUNNING;
00219 }
00220 
00221 /**
00222   * Determines if the fiber scheduler is operational.
00223   *
00224   * @return 1 if the fber scheduler is running, 0 otherwise.
00225   */
00226 int fiber_scheduler_running()
00227 {
00228     if (fiber_flags & MICROBIT_SCHEDULER_RUNNING)
00229         return 1;
00230 
00231     return 0;
00232 }
00233 
00234 /**
00235   * The timer callback, called from interrupt context once every SYSTEM_TICK_PERIOD_MS milliseconds.
00236   * This function checks to determine if any fibers blocked on the sleep queue need to be woken up
00237   * and made runnable.
00238   */
00239 void scheduler_tick()
00240 {
00241     Fiber *f = sleepQueue;
00242     Fiber *t;
00243 
00244     // Check the sleep queue, and wake up any fibers as necessary.
00245     while (f != NULL)
00246     {
00247         t = f->next;
00248 
00249         if (system_timer_current_time() >= f->context)
00250         {
00251             // Wakey wakey!
00252             dequeue_fiber(f);
00253             queue_fiber(f,&runQueue);
00254         }
00255 
00256         f = t;
00257     }
00258 }
00259 
00260 /**
00261   * Event callback. Called from an instance of MicroBitMessageBus whenever an event is raised.
00262   *
00263   * This function checks to determine if any fibers blocked on the wait queue need to be woken up
00264   * and made runnable due to the event.
00265   *
00266   * @param evt the event that has just been raised on an instance of MicroBitMessageBus.
00267   */
00268 void scheduler_event(MicroBitEvent evt)
00269 {
00270     Fiber *f = waitQueue;
00271     Fiber *t;
00272     int notifyOneComplete = 0;
00273 
00274     // This should never happen.
00275     // It is however, safe to simply ignore any events provided, as if no messageBus if recorded,
00276     // no fibers are permitted to block on events.
00277     if (messageBus == NULL)
00278         return;
00279 
00280     // Check the wait queue, and wake up any fibers as necessary.
00281     while (f != NULL)
00282     {
00283         t = f->next;
00284 
00285         // extract the event data this fiber is blocked on.
00286         uint16_t id = f->context & 0xFFFF;
00287         uint16_t value = (f->context & 0xFFFF0000) >> 16;
00288 
00289         // Special case for the NOTIFY_ONE channel...
00290         if ((evt.source == MICROBIT_ID_NOTIFY_ONE && id == MICROBIT_ID_NOTIFY) && (value == MICROBIT_EVT_ANY || value == evt.value))
00291         {
00292             if (!notifyOneComplete)
00293             {
00294                 // Wakey wakey!
00295                 dequeue_fiber(f);
00296                 queue_fiber(f,&runQueue);
00297                 notifyOneComplete = 1;
00298             }
00299         }
00300 
00301         // Normal case.
00302         else if ((id == MICROBIT_ID_ANY || id == evt.source) && (value == MICROBIT_EVT_ANY || value == evt.value))
00303         {
00304             // Wakey wakey!
00305             dequeue_fiber(f);
00306             queue_fiber(f,&runQueue);
00307         }
00308 
00309         f = t;
00310     }
00311 
00312     // Unregister this event, as we've woken up all the fibers with this match.
00313     if (evt.source != MICROBIT_ID_NOTIFY && evt.source != MICROBIT_ID_NOTIFY_ONE)
00314         messageBus->ignore(evt.source, evt.value, scheduler_event);
00315 }
00316 
00317 
00318 /**
00319   * Blocks the calling thread for the given period of time.
00320   * The calling thread will be immediateley descheduled, and placed onto a
00321   * wait queue until the requested amount of time has elapsed.
00322   *
00323   * @param t The period of time to sleep, in milliseconds.
00324   *
00325   * @note the fiber will not be be made runnable until after the elapsed time, but there
00326   * are no guarantees precisely when the fiber will next be scheduled.
00327   */
00328 void fiber_sleep(unsigned long t)
00329 {
00330     Fiber *f = currentFiber;
00331 
00332     // If the scheduler is not running, then simply perform a spin wait and exit.
00333     if (!fiber_scheduler_running())
00334     {
00335         wait_ms(t);
00336         return;
00337     }
00338 
00339     // Sleep is a blocking call, so if we're in a fork on block context,
00340     // it's time to spawn a new fiber...
00341     if (currentFiber->flags & MICROBIT_FIBER_FLAG_FOB)
00342     {
00343         // Allocate a new fiber. This will come from the fiber pool if availiable,
00344         // else a new one will be allocated on the heap.
00345         forkedFiber = getFiberContext();
00346 
00347         // If we're out of memory, there's nothing we can do.
00348         // keep running in the context of the current thread as a best effort.
00349         if (forkedFiber != NULL)
00350                 f = forkedFiber;
00351     }
00352 
00353     // Calculate and store the time we want to wake up.
00354     f->context = system_timer_current_time() + t;
00355 
00356     // Remove fiber from the run queue
00357     dequeue_fiber(f);
00358 
00359     // Add fiber to the sleep queue. We maintain strict ordering here to reduce lookup times.
00360     queue_fiber(f, &sleepQueue);
00361 
00362     // Finally, enter the scheduler.
00363     schedule();
00364 }
00365 
00366 /**
00367   * Blocks the calling thread until the specified event is raised.
00368   * The calling thread will be immediateley descheduled, and placed onto a
00369   * wait queue until the requested event is received.
00370   *
00371   * @param id The ID field of the event to listen for (e.g. MICROBIT_ID_BUTTON_A)
00372   *
00373   * @param value The value of the event to listen for (e.g. MICROBIT_BUTTON_EVT_CLICK)
00374   *
00375   * @return MICROBIT_OK, or MICROBIT_NOT_SUPPORTED if the fiber scheduler is not running, or associated with an EventModel.
00376   *
00377   * @code
00378   * fiber_wait_for_event(MICROBIT_ID_BUTTON_A, MICROBIT_BUTTON_EVT_CLICK);
00379   * @endcode
00380   *
00381   * @note the fiber will not be be made runnable until after the event is raised, but there
00382   * are no guarantees precisely when the fiber will next be scheduled.
00383   */
00384 int fiber_wait_for_event(uint16_t id, uint16_t value)
00385 {
00386     int ret = fiber_wake_on_event(id, value);
00387 
00388     if(ret == MICROBIT_OK)
00389         schedule();
00390 
00391     return ret;
00392 }
00393 
00394 /**
00395   * Configures the fiber context for the current fiber to block on an event ID
00396   * and value, but does not deschedule the fiber.
00397   *
00398   * @param id The ID field of the event to listen for (e.g. MICROBIT_ID_BUTTON_A)
00399   *
00400   * @param value The value of the event to listen for (e.g. MICROBIT_BUTTON_EVT_CLICK)
00401   *
00402   * @return MICROBIT_OK, or MICROBIT_NOT_SUPPORTED if the fiber scheduler is not running, or associated with an EventModel.
00403   *
00404   * @code
00405   * fiber_wake_on_event(MICROBIT_ID_BUTTON_A, MICROBIT_BUTTON_EVT_CLICK);
00406   *
00407   * //perform some time critical operation.
00408   *
00409   * //deschedule the current fiber manually, waiting for the previously configured event.
00410   * schedule();
00411   * @endcode
00412   */
00413 int fiber_wake_on_event(uint16_t id, uint16_t value)
00414 {
00415     Fiber *f = currentFiber;
00416 
00417     if (messageBus == NULL || !fiber_scheduler_running())
00418         return MICROBIT_NOT_SUPPORTED;
00419 
00420     // Sleep is a blocking call, so if we'r ein a fork on block context,
00421     // it's time to spawn a new fiber...
00422     if (currentFiber->flags & MICROBIT_FIBER_FLAG_FOB)
00423     {
00424         // Allocate a TCB from the new fiber. This will come from the tread pool if availiable,
00425         // else a new one will be allocated on the heap.
00426         forkedFiber = getFiberContext();
00427 
00428         // If we're out of memory, there's nothing we can do.
00429         // keep running in the context of the current thread as a best effort.
00430         if (forkedFiber != NULL)
00431                 f = forkedFiber;
00432     }
00433 
00434     // Encode the event data in the context field. It's handy having a 32 bit core. :-)
00435     f->context = value << 16 | id;
00436 
00437     // Remove ourselve from the run queue
00438     dequeue_fiber(f);
00439 
00440     // Add ourselves to the sleep queue. We maintain strict ordering here to reduce lookup times.
00441     queue_fiber(f, &waitQueue);
00442 
00443     // Register to receive this event, so we can wake up the fiber when it happens.
00444     // Special case for teh notify channel, as we always stay registered for that.
00445     if (id != MICROBIT_ID_NOTIFY && id != MICROBIT_ID_NOTIFY_ONE)
00446         messageBus->listen(id, value, scheduler_event, MESSAGE_BUS_LISTENER_IMMEDIATE);
00447 
00448     return MICROBIT_OK;
00449 }
00450 
00451 /**
00452   * Executes the given function asynchronously if necessary.
00453   *
00454   * Fibers are often used to run event handlers, however many of these event handlers are very simple functions
00455   * that complete very quickly, bringing unecessary RAM overhead.
00456   *
00457   * This function takes a snapshot of the current processor context, then attempts to optimistically call the given function directly.
00458   * We only create an additional fiber if that function performs a block operation.
00459   *
00460   * @param entry_fn The function to execute.
00461   *
00462   * @return MICROBIT_OK, or MICROBIT_INVALID_PARAMETER.
00463   */
00464 int invoke(void (*entry_fn)(void))
00465 {
00466     // Validate our parameters.
00467     if (entry_fn == NULL)
00468         return MICROBIT_INVALID_PARAMETER;
00469 
00470     if (!fiber_scheduler_running())
00471         return MICROBIT_NOT_SUPPORTED;
00472 
00473     if (currentFiber->flags & MICROBIT_FIBER_FLAG_FOB)
00474     {
00475         // If we attempt a fork on block whilst already in  fork n block context,
00476         // simply launch a fiber to deal with the request and we're done.
00477         create_fiber(entry_fn);
00478         return MICROBIT_OK;
00479     }
00480 
00481     // Snapshot current context, but also update the Link Register to
00482     // refer to our calling function.
00483     save_register_context(&currentFiber->tcb);
00484 
00485     // If we're here, there are two possibilities:
00486     // 1) We're about to attempt to execute the user code
00487     // 2) We've already tried to execute the code, it blocked, and we've backtracked.
00488 
00489     // If we're returning from the user function and we forked another fiber then cleanup and exit.
00490     if (currentFiber->flags & MICROBIT_FIBER_FLAG_PARENT)
00491     {
00492         currentFiber->flags &= ~MICROBIT_FIBER_FLAG_FOB;
00493         currentFiber->flags &= ~MICROBIT_FIBER_FLAG_PARENT;
00494         return MICROBIT_OK;
00495     }
00496 
00497     // Otherwise, we're here for the first time. Enter FORK ON BLOCK mode, and
00498     // execute the function directly. If the code tries to block, we detect this and
00499     // spawn a thread to deal with it.
00500     currentFiber->flags |= MICROBIT_FIBER_FLAG_FOB;
00501     entry_fn();
00502     currentFiber->flags &= ~MICROBIT_FIBER_FLAG_FOB;
00503 
00504     // If this is is an exiting fiber that for spawned to handle a blocking call, recycle it.
00505     // The fiber will then re-enter the scheduler, so no need for further cleanup.
00506     if (currentFiber->flags & MICROBIT_FIBER_FLAG_CHILD)
00507         release_fiber();
00508 
00509      return MICROBIT_OK;
00510 }
00511 
00512 /**
00513   * Executes the given function asynchronously if necessary, and offers the ability to provide a parameter.
00514   *
00515   * Fibers are often used to run event handlers, however many of these event handlers are very simple functions
00516   * that complete very quickly, bringing unecessary RAM. overhead
00517   *
00518   * This function takes a snapshot of the current fiber context, then attempt to optimistically call the given function directly.
00519   * We only create an additional fiber if that function performs a block operation.
00520   *
00521   * @param entry_fn The function to execute.
00522   *
00523   * @param param an untyped parameter passed into the entry_fn and completion_fn.
00524   *
00525   * @return MICROBIT_OK, or MICROBIT_INVALID_PARAMETER.
00526   */
00527 int invoke(void (*entry_fn)(void *), void *param)
00528 {
00529     // Validate our parameters.
00530     if (entry_fn == NULL)
00531         return MICROBIT_INVALID_PARAMETER;
00532 
00533     if (!fiber_scheduler_running())
00534         return MICROBIT_NOT_SUPPORTED;
00535 
00536     if (currentFiber->flags & (MICROBIT_FIBER_FLAG_FOB | MICROBIT_FIBER_FLAG_PARENT | MICROBIT_FIBER_FLAG_CHILD))
00537     {
00538         // If we attempt a fork on block whilst already in a fork on block context,
00539         // simply launch a fiber to deal with the request and we're done.
00540         create_fiber(entry_fn, param);
00541         return MICROBIT_OK;
00542     }
00543 
00544     // Snapshot current context, but also update the Link Register to
00545     // refer to our calling function.
00546     save_register_context(&currentFiber->tcb);
00547 
00548     // If we're here, there are two possibilities:
00549     // 1) We're about to attempt to execute the user code
00550     // 2) We've already tried to execute the code, it blocked, and we've backtracked.
00551 
00552     // If we're returning from the user function and we forked another fiber then cleanup and exit.
00553     if (currentFiber->flags & MICROBIT_FIBER_FLAG_PARENT)
00554     {
00555         currentFiber->flags &= ~MICROBIT_FIBER_FLAG_FOB;
00556         currentFiber->flags &= ~MICROBIT_FIBER_FLAG_PARENT;
00557         return MICROBIT_OK;
00558     }
00559 
00560     // Otherwise, we're here for the first time. Enter FORK ON BLOCK mode, and
00561     // execute the function directly. If the code tries to block, we detect this and
00562     // spawn a thread to deal with it.
00563     currentFiber->flags |= MICROBIT_FIBER_FLAG_FOB;
00564     entry_fn(param);
00565     currentFiber->flags &= ~MICROBIT_FIBER_FLAG_FOB;
00566 
00567     // If this is is an exiting fiber that for spawned to handle a blocking call, recycle it.
00568     // The fiber will then re-enter the scheduler, so no need for further cleanup.
00569     if (currentFiber->flags & MICROBIT_FIBER_FLAG_CHILD)
00570         release_fiber(param);
00571 
00572     return MICROBIT_OK;
00573 }
00574 
00575 /**
00576  * Launches a fiber.
00577  *
00578  * @param ep the entry point for the fiber.
00579  *
00580  * @param cp the completion routine after ep has finished execution
00581  */
00582 void launch_new_fiber(void (*ep)(void), void (*cp)(void))
00583 {
00584     // Execute the thread's entrypoint
00585     ep();
00586 
00587     // Execute the thread's completion routine;
00588     cp();
00589 
00590     // If we get here, then the completion routine didn't recycle the fiber... so do it anyway. :-)
00591     release_fiber();
00592 }
00593 
00594 /**
00595  * Launches a fiber with a parameter
00596  *
00597  * @param ep the entry point for the fiber.
00598  *
00599  * @param cp the completion routine after ep has finished execution
00600  *
00601  * @param pm the parameter to provide to ep and cp.
00602  */
00603 void launch_new_fiber_param(void (*ep)(void *), void (*cp)(void *), void *pm)
00604 {
00605     // Execute the thread's entrypoint.
00606     ep(pm);
00607 
00608     // Execute the thread's completion routine.
00609     cp(pm);
00610 
00611     // If we get here, then the completion routine didn't recycle the fiber... so do it anyway. :-)
00612     release_fiber(pm);
00613 }
00614 
00615 Fiber *__create_fiber(uint32_t ep, uint32_t cp, uint32_t pm, int parameterised)
00616 {
00617     // Validate our parameters.
00618     if (ep == 0 || cp == 0)
00619         return NULL;
00620 
00621     // Allocate a TCB from the new fiber. This will come from the fiber pool if availiable,
00622     // else a new one will be allocated on the heap.
00623     Fiber *newFiber = getFiberContext();
00624 
00625     // If we're out of memory, there's nothing we can do.
00626     if (newFiber == NULL)
00627         return NULL;
00628 
00629     newFiber->tcb.R0 = (uint32_t) ep;
00630     newFiber->tcb.R1 = (uint32_t) cp;
00631     newFiber->tcb.R2 = (uint32_t) pm;
00632 
00633     // Set the stack and assign the link register to refer to the appropriate entry point wrapper.
00634     newFiber->tcb.SP = CORTEX_M0_STACK_BASE - 0x04;
00635     newFiber->tcb.LR = parameterised ? (uint32_t) &launch_new_fiber_param : (uint32_t) &launch_new_fiber;
00636 
00637     // Add new fiber to the run queue.
00638     queue_fiber(newFiber, &runQueue);
00639 
00640     return newFiber;
00641 }
00642 
00643 /**
00644   * Creates a new Fiber, and launches it.
00645   *
00646   * @param entry_fn The function the new Fiber will begin execution in.
00647   *
00648   * @param completion_fn The function called when the thread completes execution of entry_fn.
00649   *                      Defaults to release_fiber.
00650   *
00651   * @return The new Fiber, or NULL if the operation could not be completed.
00652   */
00653 Fiber *create_fiber(void (*entry_fn)(void), void (*completion_fn)(void))
00654 {
00655     if (!fiber_scheduler_running())
00656         return NULL;
00657 
00658     return __create_fiber((uint32_t) entry_fn, (uint32_t)completion_fn, 0, 0);
00659 }
00660 
00661 
00662 /**
00663   * Creates a new parameterised Fiber, and launches it.
00664   *
00665   * @param entry_fn The function the new Fiber will begin execution in.
00666   *
00667   * @param param an untyped parameter passed into the entry_fn and completion_fn.
00668   *
00669   * @param completion_fn The function called when the thread completes execution of entry_fn.
00670   *                      Defaults to release_fiber.
00671   *
00672   * @return The new Fiber, or NULL if the operation could not be completed.
00673   */
00674 Fiber *create_fiber(void (*entry_fn)(void *), void *param, void (*completion_fn)(void *))
00675 {
00676     if (!fiber_scheduler_running())
00677         return NULL;
00678 
00679     return __create_fiber((uint32_t) entry_fn, (uint32_t)completion_fn, (uint32_t) param, 1);
00680 }
00681 
00682 /**
00683   * Exit point for all fibers.
00684   *
00685   * Any fiber reaching the end of its entry function will return here  for recycling.
00686   */
00687 void release_fiber(void *)
00688 {
00689     if (!fiber_scheduler_running())
00690         return;
00691 
00692     release_fiber();
00693 }
00694 
00695 /**
00696   * Exit point for all fibers.
00697   *
00698   * Any fiber reaching the end of its entry function will return here  for recycling.
00699   */
00700 void release_fiber(void)
00701 {
00702     if (!fiber_scheduler_running())
00703         return;
00704 
00705     // Remove ourselves form the runqueue.
00706     dequeue_fiber(currentFiber);
00707 
00708     // Add ourselves to the list of free fibers
00709     queue_fiber(currentFiber, &fiberPool);
00710 
00711     // Find something else to do!
00712     schedule();
00713 }
00714 
00715 /**
00716   * Resizes the stack allocation of the current fiber if necessary to hold the system stack.
00717   *
00718   * If the stack allocation is large enough to hold the current system stack, then this function does nothing.
00719   * Otherwise, the the current allocation of the fiber is freed, and a larger block is allocated.
00720   *
00721   * @param f The fiber context to verify.
00722   *
00723   * @return The stack depth of the given fiber.
00724   */
00725 void verify_stack_size(Fiber *f)
00726 {
00727     // Ensure the stack buffer is large enough to hold the stack Reallocate if necessary.
00728     uint32_t stackDepth;
00729     uint32_t bufferSize;
00730 
00731     // Calculate the stack depth.
00732     stackDepth = f->tcb.stack_base - ((uint32_t) __get_MSP());
00733 
00734     // Calculate the size of our allocated stack buffer
00735     bufferSize = f->stack_top - f->stack_bottom;
00736 
00737     // If we're too small, increase our buffer size.
00738     if (bufferSize < stackDepth)
00739     {
00740         // To ease heap churn, we choose the next largest multple of 32 bytes.
00741         bufferSize = (stackDepth + 32) & 0xffffffe0;
00742 
00743         // Release the old memory
00744         if (f->stack_bottom != 0)
00745             free((void *)f->stack_bottom);
00746 
00747         // Allocate a new one of the appropriate size.
00748         f->stack_bottom = (uint32_t) malloc(bufferSize);
00749 
00750         // Recalculate where the top of the stack is and we're done.
00751         f->stack_top = f->stack_bottom + bufferSize;
00752     }
00753 }
00754 
00755 /**
00756   * Determines if any fibers are waiting to be scheduled.
00757   *
00758   * @return The number of fibers currently on the run queue
00759   */
00760 int scheduler_runqueue_empty()
00761 {
00762     return (runQueue == NULL);
00763 }
00764 
00765 /**
00766   * Calls the Fiber scheduler.
00767   * The calling Fiber will likely be blocked, and control given to another waiting fiber.
00768   * Call this function to yield control of the processor when you have nothing more to do.
00769   */
00770 void schedule()
00771 {
00772     if (!fiber_scheduler_running())
00773         return;
00774 
00775     // First, take a reference to the currently running fiber;
00776     Fiber *oldFiber = currentFiber;
00777 
00778     // First, see if we're in Fork on Block context. If so, we simply want to store the full context
00779     // of the currently running thread in a newly created fiber, and restore the context of the
00780     // currently running fiber, back to the point where it entered FOB.
00781 
00782     if (currentFiber->flags & MICROBIT_FIBER_FLAG_FOB)
00783     {
00784         // Record that the fibers have a parent/child relationship
00785         currentFiber->flags |= MICROBIT_FIBER_FLAG_PARENT;
00786         forkedFiber->flags |= MICROBIT_FIBER_FLAG_CHILD;
00787 
00788         // Define the stack base of the forked fiber to be align with the entry point of the parent fiber
00789         forkedFiber->tcb.stack_base = currentFiber->tcb.SP;
00790 
00791         // Ensure the stack allocation of the new fiber is large enough
00792         verify_stack_size(forkedFiber);
00793 
00794         // Store the full context of this fiber.
00795         save_context(&forkedFiber->tcb, forkedFiber->stack_top);
00796 
00797         // We may now be either the newly created thread, or the one that created it.
00798         // if the MICROBIT_FIBER_FLAG_PARENT flag is still set, we're the old thread, so
00799         // restore the current fiber to its stored context and we're done.
00800         if (currentFiber->flags & MICROBIT_FIBER_FLAG_PARENT)
00801             restore_register_context(&currentFiber->tcb);
00802 
00803         // If we're the new thread, we must have been unblocked by the scheduler, so simply return
00804         // and continue processing.
00805         return;
00806     }
00807 
00808     // We're in a normal scheduling context, so perform a round robin algorithm across runnable fibers.
00809     // OK - if we've nothing to do, then run the IDLE task (power saving sleep)
00810     if (runQueue == NULL)
00811         currentFiber = idleFiber;
00812 
00813     else if (currentFiber->queue == &runQueue)
00814         // If the current fiber is on the run queue, round robin.
00815         currentFiber = currentFiber->next == NULL ? runQueue : currentFiber->next;
00816 
00817     else
00818         // Otherwise, just pick the head of the run queue.
00819         currentFiber = runQueue;
00820 
00821     if (currentFiber == idleFiber && oldFiber->flags & MICROBIT_FIBER_FLAG_DO_NOT_PAGE)
00822     {
00823         // Run the idle task right here using the old fiber's stack.
00824         // Keep idling while the runqueue is empty, or there is data to process.
00825 
00826         // Run in the context of the original fiber, to preserve state of flags...
00827         // as we are running on top of this fiber's stack.
00828         currentFiber = oldFiber;
00829 
00830         do
00831         {
00832             idle();
00833         }
00834         while (runQueue == NULL);
00835 
00836         // Switch to a non-idle fiber.
00837         // If this fiber is the same as the old one then there'll be no switching at all.
00838         currentFiber = runQueue;
00839     }
00840 
00841     // Swap to the context of the chosen fiber, and we're done.
00842     // Don't bother with the overhead of switching if there's only one fiber on the runqueue!
00843     if (currentFiber != oldFiber)
00844     {
00845         // Special case for the idle task, as we don't maintain a stack context (just to save memory).
00846         if (currentFiber == idleFiber)
00847         {
00848             idleFiber->tcb.SP = CORTEX_M0_STACK_BASE - 0x04;
00849             idleFiber->tcb.LR = (uint32_t) &idle_task;
00850         }
00851 
00852         if (oldFiber == idleFiber)
00853         {
00854             // Just swap in the new fiber, and discard changes to stack and register context.
00855             swap_context(NULL, &currentFiber->tcb, 0, currentFiber->stack_top);
00856         }
00857         else
00858         {
00859             // Ensure the stack allocation of the fiber being scheduled out is large enough
00860             verify_stack_size(oldFiber);
00861 
00862             // Schedule in the new fiber.
00863             swap_context(&oldFiber->tcb, &currentFiber->tcb, oldFiber->stack_top, currentFiber->stack_top);
00864         }
00865     }
00866 }
00867 
00868 /**
00869   * Adds a component to the array of idle thread components, which are processed
00870   * when the run queue is empty.
00871   *
00872   * The system timer will poll isIdleCallbackNeeded on each component to determine
00873   * if the scheduler should schedule the idle_task imminently.
00874   *
00875   * @param component The component to add to the array.
00876   *
00877   * @return MICROBIT_OK on success or MICROBIT_NO_RESOURCES if the fiber components array is full.
00878   *
00879   * @code
00880   * MicroBitI2C i2c(I2C_SDA0, I2C_SCL0);
00881   *
00882   * // heap allocated - otherwise it will be paged out!
00883   * MicroBitAccelerometer* accelerometer = new MicroBitAccelerometer(i2c);
00884   *
00885   * fiber_add_idle_component(accelerometer);
00886   * @endcode
00887   */
00888 int fiber_add_idle_component(MicroBitComponent *component)
00889 {
00890     int i = 0;
00891 
00892     while(idleThreadComponents[i] != NULL && i < MICROBIT_IDLE_COMPONENTS)
00893         i++;
00894 
00895     if(i == MICROBIT_IDLE_COMPONENTS)
00896         return MICROBIT_NO_RESOURCES;
00897 
00898     idleThreadComponents[i] = component;
00899 
00900     return MICROBIT_OK;
00901 }
00902 
00903 /**
00904   * Remove a component from the array of idle thread components
00905   *
00906   * @param component The component to remove from the idle component array.
00907   *
00908   * @return MICROBIT_OK on success. MICROBIT_INVALID_PARAMETER is returned if the given component has not been previously added.
00909   *
00910   * @code
00911   * MicroBitI2C i2c(I2C_SDA0, I2C_SCL0);
00912   *
00913   * // heap allocated - otherwise it will be paged out!
00914   * MicroBitAccelerometer* accelerometer = new MicroBitAccelerometer(i2c);
00915   *
00916   * fiber_add_idle_component(accelerometer);
00917   *
00918   * fiber_remove_idle_component(accelerometer);
00919   * @endcode
00920   */
00921 int fiber_remove_idle_component(MicroBitComponent *component)
00922 {
00923     int i = 0;
00924 
00925     while(idleThreadComponents[i] != component && i < MICROBIT_IDLE_COMPONENTS)
00926         i++;
00927 
00928     if(i == MICROBIT_IDLE_COMPONENTS)
00929         return MICROBIT_INVALID_PARAMETER;
00930 
00931     idleThreadComponents[i] = NULL;
00932 
00933     return MICROBIT_OK;
00934 }
00935 
00936 /**
00937   * Set of tasks to perform when idle.
00938   * Service any background tasks that are required, and attempt a power efficient sleep.
00939   */
00940 void idle()
00941 {
00942     // Service background tasks
00943     for(int i = 0; i < MICROBIT_IDLE_COMPONENTS; i++)
00944         if(idleThreadComponents[i] != NULL)
00945             idleThreadComponents[i]->idleTick();
00946 
00947     // If the above did create any useful work, enter power efficient sleep.
00948     if(scheduler_runqueue_empty())
00949         __WFE();
00950 }
00951 
00952 /**
00953   * The idle task, which is called when the runtime has no fibers that require execution.
00954   *
00955   * This function typically calls idle().
00956   */
00957 void idle_task()
00958 {
00959     while(1)
00960     {
00961         idle();
00962         schedule();
00963     }
00964 }