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.
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're in 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         {
00432             f = forkedFiber;
00433             dequeue_fiber(f);
00434             queue_fiber(f, &runQueue);
00435             schedule();
00436         }
00437     }
00438 
00439     // Encode the event data in the context field. It's handy having a 32 bit core. :-)
00440     f->context = value << 16 | id;
00441 
00442     // Remove ourselves from the run queue
00443     dequeue_fiber(f);
00444 
00445     // Add ourselves to the sleep queue. We maintain strict ordering here to reduce lookup times.
00446     queue_fiber(f, &waitQueue);
00447 
00448     // Register to receive this event, so we can wake up the fiber when it happens.
00449     // Special case for the notify channel, as we always stay registered for that.
00450     if (id != MICROBIT_ID_NOTIFY && id != MICROBIT_ID_NOTIFY_ONE)
00451         messageBus->listen(id, value, scheduler_event, MESSAGE_BUS_LISTENER_IMMEDIATE);
00452 
00453     return MICROBIT_OK;
00454 }
00455 
00456 /**
00457   * Executes the given function asynchronously if necessary.
00458   *
00459   * Fibers are often used to run event handlers, however many of these event handlers are very simple functions
00460   * that complete very quickly, bringing unecessary RAM overhead.
00461   *
00462   * This function takes a snapshot of the current processor context, then attempts to optimistically call the given function directly.
00463   * We only create an additional fiber if that function performs a block operation.
00464   *
00465   * @param entry_fn The function to execute.
00466   *
00467   * @return MICROBIT_OK, or MICROBIT_INVALID_PARAMETER.
00468   */
00469 int invoke(void (*entry_fn)(void))
00470 {
00471     // Validate our parameters.
00472     if (entry_fn == NULL)
00473         return MICROBIT_INVALID_PARAMETER;
00474 
00475     if (!fiber_scheduler_running())
00476         return MICROBIT_NOT_SUPPORTED;
00477 
00478     if (currentFiber->flags & MICROBIT_FIBER_FLAG_FOB)
00479     {
00480         // If we attempt a fork on block whilst already in  fork n block context,
00481         // simply launch a fiber to deal with the request and we're done.
00482         create_fiber(entry_fn);
00483         return MICROBIT_OK;
00484     }
00485 
00486     // Snapshot current context, but also update the Link Register to
00487     // refer to our calling function.
00488     save_register_context(&currentFiber->tcb);
00489 
00490     // If we're here, there are two possibilities:
00491     // 1) We're about to attempt to execute the user code
00492     // 2) We've already tried to execute the code, it blocked, and we've backtracked.
00493 
00494     // If we're returning from the user function and we forked another fiber then cleanup and exit.
00495     if (currentFiber->flags & MICROBIT_FIBER_FLAG_PARENT)
00496     {
00497         currentFiber->flags &= ~MICROBIT_FIBER_FLAG_FOB;
00498         currentFiber->flags &= ~MICROBIT_FIBER_FLAG_PARENT;
00499         return MICROBIT_OK;
00500     }
00501 
00502     // Otherwise, we're here for the first time. Enter FORK ON BLOCK mode, and
00503     // execute the function directly. If the code tries to block, we detect this and
00504     // spawn a thread to deal with it.
00505     currentFiber->flags |= MICROBIT_FIBER_FLAG_FOB;
00506     entry_fn();
00507     currentFiber->flags &= ~MICROBIT_FIBER_FLAG_FOB;
00508 
00509     // If this is is an exiting fiber that for spawned to handle a blocking call, recycle it.
00510     // The fiber will then re-enter the scheduler, so no need for further cleanup.
00511     if (currentFiber->flags & MICROBIT_FIBER_FLAG_CHILD)
00512         release_fiber();
00513 
00514      return MICROBIT_OK;
00515 }
00516 
00517 /**
00518   * Executes the given function asynchronously if necessary, and offers the ability to provide a parameter.
00519   *
00520   * Fibers are often used to run event handlers, however many of these event handlers are very simple functions
00521   * that complete very quickly, bringing unecessary RAM. overhead
00522   *
00523   * This function takes a snapshot of the current fiber context, then attempt to optimistically call the given function directly.
00524   * We only create an additional fiber if that function performs a block operation.
00525   *
00526   * @param entry_fn The function to execute.
00527   *
00528   * @param param an untyped parameter passed into the entry_fn and completion_fn.
00529   *
00530   * @return MICROBIT_OK, or MICROBIT_INVALID_PARAMETER.
00531   */
00532 int invoke(void (*entry_fn)(void *), void *param)
00533 {
00534     // Validate our parameters.
00535     if (entry_fn == NULL)
00536         return MICROBIT_INVALID_PARAMETER;
00537 
00538     if (!fiber_scheduler_running())
00539         return MICROBIT_NOT_SUPPORTED;
00540 
00541     if (currentFiber->flags & (MICROBIT_FIBER_FLAG_FOB | MICROBIT_FIBER_FLAG_PARENT | MICROBIT_FIBER_FLAG_CHILD))
00542     {
00543         // If we attempt a fork on block whilst already in a fork on block context,
00544         // simply launch a fiber to deal with the request and we're done.
00545         create_fiber(entry_fn, param);
00546         return MICROBIT_OK;
00547     }
00548 
00549     // Snapshot current context, but also update the Link Register to
00550     // refer to our calling function.
00551     save_register_context(&currentFiber->tcb);
00552 
00553     // If we're here, there are two possibilities:
00554     // 1) We're about to attempt to execute the user code
00555     // 2) We've already tried to execute the code, it blocked, and we've backtracked.
00556 
00557     // If we're returning from the user function and we forked another fiber then cleanup and exit.
00558     if (currentFiber->flags & MICROBIT_FIBER_FLAG_PARENT)
00559     {
00560         currentFiber->flags &= ~MICROBIT_FIBER_FLAG_FOB;
00561         currentFiber->flags &= ~MICROBIT_FIBER_FLAG_PARENT;
00562         return MICROBIT_OK;
00563     }
00564 
00565     // Otherwise, we're here for the first time. Enter FORK ON BLOCK mode, and
00566     // execute the function directly. If the code tries to block, we detect this and
00567     // spawn a thread to deal with it.
00568     currentFiber->flags |= MICROBIT_FIBER_FLAG_FOB;
00569     entry_fn(param);
00570     currentFiber->flags &= ~MICROBIT_FIBER_FLAG_FOB;
00571 
00572     // If this is is an exiting fiber that for spawned to handle a blocking call, recycle it.
00573     // The fiber will then re-enter the scheduler, so no need for further cleanup.
00574     if (currentFiber->flags & MICROBIT_FIBER_FLAG_CHILD)
00575         release_fiber(param);
00576 
00577     return MICROBIT_OK;
00578 }
00579 
00580 /**
00581  * Launches a fiber.
00582  *
00583  * @param ep the entry point for the fiber.
00584  *
00585  * @param cp the completion routine after ep has finished execution
00586  */
00587 void launch_new_fiber(void (*ep)(void), void (*cp)(void))
00588 {
00589     // Execute the thread's entrypoint
00590     ep();
00591 
00592     // Execute the thread's completion routine;
00593     cp();
00594 
00595     // If we get here, then the completion routine didn't recycle the fiber... so do it anyway. :-)
00596     release_fiber();
00597 }
00598 
00599 /**
00600  * Launches a fiber with a parameter
00601  *
00602  * @param ep the entry point for the fiber.
00603  *
00604  * @param cp the completion routine after ep has finished execution
00605  *
00606  * @param pm the parameter to provide to ep and cp.
00607  */
00608 void launch_new_fiber_param(void (*ep)(void *), void (*cp)(void *), void *pm)
00609 {
00610     // Execute the thread's entrypoint.
00611     ep(pm);
00612 
00613     // Execute the thread's completion routine.
00614     cp(pm);
00615 
00616     // If we get here, then the completion routine didn't recycle the fiber... so do it anyway. :-)
00617     release_fiber(pm);
00618 }
00619 
00620 Fiber *__create_fiber(uint32_t ep, uint32_t cp, uint32_t pm, int parameterised)
00621 {
00622     // Validate our parameters.
00623     if (ep == 0 || cp == 0)
00624         return NULL;
00625 
00626     // Allocate a TCB from the new fiber. This will come from the fiber pool if availiable,
00627     // else a new one will be allocated on the heap.
00628     Fiber *newFiber = getFiberContext();
00629 
00630     // If we're out of memory, there's nothing we can do.
00631     if (newFiber == NULL)
00632         return NULL;
00633 
00634     newFiber->tcb.R0 = (uint32_t) ep;
00635     newFiber->tcb.R1 = (uint32_t) cp;
00636     newFiber->tcb.R2 = (uint32_t) pm;
00637 
00638     // Set the stack and assign the link register to refer to the appropriate entry point wrapper.
00639     newFiber->tcb.SP = CORTEX_M0_STACK_BASE - 0x04;
00640     newFiber->tcb.LR = parameterised ? (uint32_t) &launch_new_fiber_param : (uint32_t) &launch_new_fiber;
00641 
00642     // Add new fiber to the run queue.
00643     queue_fiber(newFiber, &runQueue);
00644 
00645     return newFiber;
00646 }
00647 
00648 /**
00649   * Creates a new Fiber, and launches it.
00650   *
00651   * @param entry_fn The function the new Fiber will begin execution in.
00652   *
00653   * @param completion_fn The function called when the thread completes execution of entry_fn.
00654   *                      Defaults to release_fiber.
00655   *
00656   * @return The new Fiber, or NULL if the operation could not be completed.
00657   */
00658 Fiber *create_fiber(void (*entry_fn)(void), void (*completion_fn)(void))
00659 {
00660     if (!fiber_scheduler_running())
00661         return NULL;
00662 
00663     return __create_fiber((uint32_t) entry_fn, (uint32_t)completion_fn, 0, 0);
00664 }
00665 
00666 
00667 /**
00668   * Creates a new parameterised Fiber, and launches it.
00669   *
00670   * @param entry_fn The function the new Fiber will begin execution in.
00671   *
00672   * @param param an untyped parameter passed into the entry_fn and completion_fn.
00673   *
00674   * @param completion_fn The function called when the thread completes execution of entry_fn.
00675   *                      Defaults to release_fiber.
00676   *
00677   * @return The new Fiber, or NULL if the operation could not be completed.
00678   */
00679 Fiber *create_fiber(void (*entry_fn)(void *), void *param, void (*completion_fn)(void *))
00680 {
00681     if (!fiber_scheduler_running())
00682         return NULL;
00683 
00684     return __create_fiber((uint32_t) entry_fn, (uint32_t)completion_fn, (uint32_t) param, 1);
00685 }
00686 
00687 /**
00688   * Exit point for all fibers.
00689   *
00690   * Any fiber reaching the end of its entry function will return here  for recycling.
00691   */
00692 void release_fiber(void *)
00693 {
00694     if (!fiber_scheduler_running())
00695         return;
00696 
00697     release_fiber();
00698 }
00699 
00700 /**
00701   * Exit point for all fibers.
00702   *
00703   * Any fiber reaching the end of its entry function will return here  for recycling.
00704   */
00705 void release_fiber(void)
00706 {
00707     if (!fiber_scheduler_running())
00708         return;
00709 
00710     // Remove ourselves form the runqueue.
00711     dequeue_fiber(currentFiber);
00712 
00713     // Add ourselves to the list of free fibers
00714     queue_fiber(currentFiber, &fiberPool);
00715 
00716     // Find something else to do!
00717     schedule();
00718 }
00719 
00720 /**
00721   * Resizes the stack allocation of the current fiber if necessary to hold the system stack.
00722   *
00723   * If the stack allocation is large enough to hold the current system stack, then this function does nothing.
00724   * Otherwise, the the current allocation of the fiber is freed, and a larger block is allocated.
00725   *
00726   * @param f The fiber context to verify.
00727   *
00728   * @return The stack depth of the given fiber.
00729   */
00730 void verify_stack_size(Fiber *f)
00731 {
00732     // Ensure the stack buffer is large enough to hold the stack Reallocate if necessary.
00733     uint32_t stackDepth;
00734     uint32_t bufferSize;
00735 
00736     // Calculate the stack depth.
00737     stackDepth = f->tcb.stack_base - ((uint32_t) __get_MSP());
00738 
00739     // Calculate the size of our allocated stack buffer
00740     bufferSize = f->stack_top - f->stack_bottom;
00741 
00742     // If we're too small, increase our buffer size.
00743     if (bufferSize < stackDepth)
00744     {
00745         // To ease heap churn, we choose the next largest multple of 32 bytes.
00746         bufferSize = (stackDepth + 32) & 0xffffffe0;
00747 
00748         // Release the old memory
00749         if (f->stack_bottom != 0)
00750             free((void *)f->stack_bottom);
00751 
00752         // Allocate a new one of the appropriate size.
00753         f->stack_bottom = (uint32_t) malloc(bufferSize);
00754 
00755         // Recalculate where the top of the stack is and we're done.
00756         f->stack_top = f->stack_bottom + bufferSize;
00757     }
00758 }
00759 
00760 /**
00761   * Determines if any fibers are waiting to be scheduled.
00762   *
00763   * @return The number of fibers currently on the run queue
00764   */
00765 int scheduler_runqueue_empty()
00766 {
00767     return (runQueue == NULL);
00768 }
00769 
00770 /**
00771   * Calls the Fiber scheduler.
00772   * The calling Fiber will likely be blocked, and control given to another waiting fiber.
00773   * Call this function to yield control of the processor when you have nothing more to do.
00774   */
00775 void schedule()
00776 {
00777     if (!fiber_scheduler_running())
00778         return;
00779 
00780     // First, take a reference to the currently running fiber;
00781     Fiber *oldFiber = currentFiber;
00782 
00783     // First, see if we're in Fork on Block context. If so, we simply want to store the full context
00784     // of the currently running thread in a newly created fiber, and restore the context of the
00785     // currently running fiber, back to the point where it entered FOB.
00786 
00787     if (currentFiber->flags & MICROBIT_FIBER_FLAG_FOB)
00788     {
00789         // Record that the fibers have a parent/child relationship
00790         currentFiber->flags |= MICROBIT_FIBER_FLAG_PARENT;
00791         forkedFiber->flags |= MICROBIT_FIBER_FLAG_CHILD;
00792 
00793         // Define the stack base of the forked fiber to be align with the entry point of the parent fiber
00794         forkedFiber->tcb.stack_base = currentFiber->tcb.SP;
00795 
00796         // Ensure the stack allocation of the new fiber is large enough
00797         verify_stack_size(forkedFiber);
00798 
00799         // Store the full context of this fiber.
00800         save_context(&forkedFiber->tcb, forkedFiber->stack_top);
00801 
00802         // We may now be either the newly created thread, or the one that created it.
00803         // if the MICROBIT_FIBER_FLAG_PARENT flag is still set, we're the old thread, so
00804         // restore the current fiber to its stored context and we're done.
00805         if (currentFiber->flags & MICROBIT_FIBER_FLAG_PARENT)
00806             restore_register_context(&currentFiber->tcb);
00807 
00808         // If we're the new thread, we must have been unblocked by the scheduler, so simply return
00809         // and continue processing.
00810         return;
00811     }
00812 
00813     // We're in a normal scheduling context, so perform a round robin algorithm across runnable fibers.
00814     // OK - if we've nothing to do, then run the IDLE task (power saving sleep)
00815     if (runQueue == NULL)
00816         currentFiber = idleFiber;
00817 
00818     else if (currentFiber->queue == &runQueue)
00819         // If the current fiber is on the run queue, round robin.
00820         currentFiber = currentFiber->next == NULL ? runQueue : currentFiber->next;
00821 
00822     else
00823         // Otherwise, just pick the head of the run queue.
00824         currentFiber = runQueue;
00825 
00826     if (currentFiber == idleFiber && oldFiber->flags & MICROBIT_FIBER_FLAG_DO_NOT_PAGE)
00827     {
00828         // Run the idle task right here using the old fiber's stack.
00829         // Keep idling while the runqueue is empty, or there is data to process.
00830 
00831         // Run in the context of the original fiber, to preserve state of flags...
00832         // as we are running on top of this fiber's stack.
00833         currentFiber = oldFiber;
00834 
00835         do
00836         {
00837             idle();
00838         }
00839         while (runQueue == NULL);
00840 
00841         // Switch to a non-idle fiber.
00842         // If this fiber is the same as the old one then there'll be no switching at all.
00843         currentFiber = runQueue;
00844     }
00845 
00846     // Swap to the context of the chosen fiber, and we're done.
00847     // Don't bother with the overhead of switching if there's only one fiber on the runqueue!
00848     if (currentFiber != oldFiber)
00849     {
00850         // Special case for the idle task, as we don't maintain a stack context (just to save memory).
00851         if (currentFiber == idleFiber)
00852         {
00853             idleFiber->tcb.SP = CORTEX_M0_STACK_BASE - 0x04;
00854             idleFiber->tcb.LR = (uint32_t) &idle_task;
00855         }
00856 
00857         if (oldFiber == idleFiber)
00858         {
00859             // Just swap in the new fiber, and discard changes to stack and register context.
00860             swap_context(NULL, &currentFiber->tcb, 0, currentFiber->stack_top);
00861         }
00862         else
00863         {
00864             // Ensure the stack allocation of the fiber being scheduled out is large enough
00865             verify_stack_size(oldFiber);
00866 
00867             // Schedule in the new fiber.
00868             swap_context(&oldFiber->tcb, &currentFiber->tcb, oldFiber->stack_top, currentFiber->stack_top);
00869         }
00870     }
00871 }
00872 
00873 /**
00874   * Adds a component to the array of idle thread components, which are processed
00875   * when the run queue is empty.
00876   *
00877   * @param component The component to add to the array.
00878   * @return MICROBIT_OK on success or MICROBIT_NO_RESOURCES if the fiber components array is full.
00879   */
00880 int fiber_add_idle_component(MicroBitComponent *component)
00881 {
00882     int i = 0;
00883 
00884     while(idleThreadComponents[i] != NULL && i < MICROBIT_IDLE_COMPONENTS)
00885         i++;
00886 
00887     if(i == MICROBIT_IDLE_COMPONENTS)
00888         return MICROBIT_NO_RESOURCES;
00889 
00890     idleThreadComponents[i] = component;
00891 
00892     return MICROBIT_OK;
00893 }
00894 
00895 /**
00896   * remove a component from the array of idle thread components
00897   *
00898   * @param component the component to remove from the idle component array.
00899   * @return MICROBIT_OK on success. MICROBIT_INVALID_PARAMETER is returned if the given component has not been previously added.
00900   */
00901 int fiber_remove_idle_component(MicroBitComponent *component)
00902 {
00903     int i = 0;
00904 
00905     while(idleThreadComponents[i] != component && i < MICROBIT_IDLE_COMPONENTS)
00906         i++;
00907 
00908     if(i == MICROBIT_IDLE_COMPONENTS)
00909         return MICROBIT_INVALID_PARAMETER;
00910 
00911     idleThreadComponents[i] = NULL;
00912 
00913     return MICROBIT_OK;
00914 }
00915 
00916 /**
00917   * Set of tasks to perform when idle.
00918   * Service any background tasks that are required, and attempt a power efficient sleep.
00919   */
00920 void idle()
00921 {
00922     // Service background tasks
00923     for(int i = 0; i < MICROBIT_IDLE_COMPONENTS; i++)
00924         if(idleThreadComponents[i] != NULL)
00925             idleThreadComponents[i]->idleTick();
00926 
00927     // If the above did create any useful work, enter power efficient sleep.
00928     if(scheduler_runqueue_empty())
00929         __WFE();
00930 }
00931 
00932 /**
00933   * The idle task, which is called when the runtime has no fibers that require execution.
00934   *
00935   * This function typically calls idle().
00936   */
00937 void idle_task()
00938 {
00939     while(1)
00940     {
00941         idle();
00942         schedule();
00943     }
00944 }