MicroBitFiber.cpp

00001 /**
00002   * The MicroBit Fiber scheduler.
00003   *
00004   * This lightweight, non-preemptive scheduler provides a simple threading mechanism for two main purposes:
00005   *
00006   * 1) To provide a clean abstraction for application languages to use when building async behaviour (callbacks).
00007   * 2) To provide ISR decoupling for Messagebus events generted in an ISR context.
00008   */
00009   
00010 #include "MicroBitFiber.h"
00011 
00012 /*
00013  * Statically allocated values used to create and destroy Fibers.
00014  * required to be defined here to allow persistence during context switches.
00015  */
00016  
00017 /*
00018  * Scheduler state.
00019  */
00020  
00021 Fiber *currentFiber = NULL;                 // The context in which the current fiber is executing.
00022 Fiber *runQueue = NULL;                     // The list of runnable fibers.
00023 Fiber *sleepQueue = NULL;                   // The list of blocked fibers waiting on a fiber_sleep() operation.
00024 Fiber *idle = NULL;                         // IDLE task - performs a power efficient sleep.
00025 Fiber *fiberPool = NULL;                    // Pool of unused fibers, just waiting for a job to do.
00026 
00027 Cortex_M0_TCB  *emptyContext = NULL;        // Initialized context for fiber entry state.
00028 
00029 /*
00030  * Time since power on. Measured in milliseconds.
00031  * When stored as an unsigned long, this gives us approx 50 days between rollover, which is ample. :-)
00032  */
00033 unsigned long ticks = 0;
00034 
00035 /**
00036   * Utility function to add the currenty running fiber to the given queue. 
00037   * Perform a simple add at the head, to avoid complexity,
00038   * Queues are normally very short, so maintaining a doubly linked, sorted list typically outweighs the cost of
00039   * brute force searching.
00040   *
00041   * @param f The fiber to add to the queue
00042   * @param queue The run queue to add the fiber to.
00043   */
00044 void queue_fiber(Fiber *f, Fiber **queue)
00045 {
00046     __disable_irq();
00047 
00048     f->queue = queue;
00049     f->next = *queue;
00050     f->prev = NULL;
00051     
00052     if(*queue != NULL)
00053         (*queue)->prev = f;
00054         
00055     *queue = f;    
00056 
00057     __enable_irq();
00058 }
00059 
00060 /**
00061   * Utility function to the given fiber from whichever queue it is currently stored on. 
00062   * @param f the fiber to remove.
00063   */
00064 void dequeue_fiber(Fiber *f)
00065 {
00066     __disable_irq();
00067     
00068     if (f->prev != NULL)
00069         f->prev->next = f->next;
00070     else
00071         *(f->queue) = f->next;
00072     
00073     if(f->next)
00074         f->next->prev = f->prev;
00075         
00076     f->next = NULL;
00077     f->prev = NULL;
00078     f->queue = NULL;
00079     
00080     __enable_irq();
00081 
00082 }
00083 
00084 
00085 /**
00086   * Initialises the Fiber scheduler. 
00087   * Creates a Fiber context around the calling thread, and adds it to the run queue as the current thread.
00088   *
00089   * This function must be called once only from the main thread, and before any other Fiber operation.
00090   */
00091 void scheduler_init()
00092 {
00093     // Create a new fiber context
00094     currentFiber = new Fiber();
00095     currentFiber->stack_bottom = (uint32_t) malloc(FIBER_STACK_SIZE);
00096     currentFiber->stack_top = ((uint32_t) currentFiber->stack_bottom) + FIBER_STACK_SIZE;
00097     
00098     // Add ourselves to the run queue.
00099     queue_fiber(currentFiber, &runQueue);
00100  
00101     // Build a fiber context around the current thread.
00102     swap_context(&currentFiber->tcb, &currentFiber->tcb, currentFiber->stack_top, currentFiber->stack_top);    
00103     
00104     // Create the IDLE task. This will actually scheduk the IDLE task, but it will immediately yeld back to us.
00105     // Remove it from the run queue though, as IDLE is a special case.
00106     idle = create_fiber(idle_task);    
00107     dequeue_fiber(idle);    
00108 }
00109 
00110 /**
00111   * Timer callback. Called from interrupt context, once every FIBER_TICK_PERIOD_MS milliseconds.
00112   * Simply checks to determine if any fibers blocked on the sleep queue need to be woken up 
00113   * and made runnable.
00114   */
00115 void scheduler_tick()
00116 {
00117     Fiber *f = sleepQueue;
00118     Fiber *t;
00119     
00120     // increment our real-time counter.
00121     ticks += FIBER_TICK_PERIOD_MS;
00122     
00123     // Check the sleep queue, and wake up any fibers as necessary.
00124     while (f != NULL)
00125     {
00126         t = f->next;        
00127         
00128         if (ticks >= f->context)
00129         {
00130             // Wakey wakey!
00131             dequeue_fiber(f);
00132             queue_fiber(f,&runQueue);
00133         }
00134         
00135         f = t;
00136     }
00137 }
00138 
00139 /**
00140   * Blocks the calling thread for the given period of time.
00141   * The calling thread will be immediatley descheduled, and placed onto a 
00142   * wait queue until the requested amount of time has elapsed. 
00143   * 
00144   * n.b. the fiber will not be be made runnable until after the elasped time, but there
00145   * are no guarantees precisely when the fiber will next be scheduled.
00146   *
00147   * @param t The period of time to sleep, in milliseconds.
00148   */
00149 void fiber_sleep(unsigned long t)
00150 {
00151     // Calculate and store the time we want to wake up.
00152     currentFiber->context = ticks + t;
00153     
00154     // Remove ourselve from the run queue
00155     dequeue_fiber(currentFiber);
00156         
00157     // Add ourselves to the sleep queue. We maintain strict ordering here to reduce lookup times.
00158     queue_fiber(currentFiber, &sleepQueue);
00159     
00160     // Finally, enter the scheduler.
00161     schedule();
00162 }
00163 
00164 Fiber *getFiberContext()
00165 {
00166     Fiber *f;
00167     
00168     __disable_irq();
00169         
00170     if (fiberPool != NULL)
00171     {
00172         f = fiberPool;
00173         dequeue_fiber(f);
00174         
00175         // dequeue_fiber() exits with irqs enablesd, so no need to do this again!
00176     }
00177     else
00178     {
00179         __enable_irq();
00180         
00181         f = new Fiber();
00182         f->stack_bottom = (uint32_t) malloc(FIBER_STACK_SIZE);
00183         f->stack_top = f->stack_bottom + FIBER_STACK_SIZE;
00184     }    
00185     
00186     return f;
00187 }
00188 
00189 /**
00190  * Creates a new Fiber, and launches it.
00191   *
00192   * @param entry_fn The function the new Fiber will begin execution in.
00193   * @return The new Fiber.
00194   */
00195 Fiber *create_fiber(void (*entry_fn)(void))
00196 {
00197     Fiber *newFiber = getFiberContext();
00198     *((uint32_t *)newFiber->stack_bottom) = (uint32_t) entry_fn;
00199 
00200     // Use cache fiber state if we have it. This is faster, and safer if we're called from
00201     // an interrupt context.
00202     if (emptyContext != NULL)
00203     {
00204         memcpy(&newFiber->tcb, emptyContext, sizeof(Cortex_M0_TCB));
00205     }
00206     else
00207     {
00208         // Otherwise, initialize the TCB from the current context.
00209         save_context(&newFiber->tcb, newFiber->stack_top);
00210         
00211         // Assign the new stack pointer and entry point.
00212         newFiber->tcb.SP = CORTEX_M0_STACK_BASE;    
00213         newFiber->tcb.LR = (uint32_t) &&LAUNCH_NEW_FIBER;
00214         
00215         // Store this context for later use.
00216         emptyContext = (Cortex_M0_TCB *) malloc (sizeof(Cortex_M0_TCB));
00217         memcpy(emptyContext, &newFiber->tcb, sizeof(Cortex_M0_TCB));
00218     }
00219     
00220     // Add new fiber to the run queue.
00221     queue_fiber(newFiber, &runQueue);
00222         
00223     return newFiber;
00224 
00225 LAUNCH_NEW_FIBER:     
00226  
00227     // Launch into the entry point, now we're in the correct context. 
00228     (*(void(*)())(*((uint32_t *)currentFiber->stack_bottom)))();
00229     
00230     // Garbage collect the fiber once it exits.    
00231     release_fiber();
00232         
00233     return NULL;
00234 }
00235 
00236 
00237 /**
00238   * Exit point for all fibers.
00239   * Any fiber reaching the end of its entry function will return here  for recycling.
00240   *
00241   * TODO: Build a Fiber Pool, rather than just leak memory here. :-)
00242   */
00243 void release_fiber(void)
00244 {  
00245     // Remove ourselves form the runqueue.
00246     dequeue_fiber(currentFiber);
00247     queue_fiber(currentFiber, &fiberPool);
00248     
00249     // Find something else to do!
00250     schedule();   
00251 }
00252 
00253 /**
00254   * Calls the Fiber scheduler.
00255   * The calling Fiber will likely be blocked, and control given to another waiting fiber.
00256   * Call this to yield control of the processor when you have nothing more to do.
00257   */
00258 void schedule()
00259 {
00260     // Just round robin for now!
00261     Fiber *oldFiber = currentFiber;
00262 
00263     // OK - if we've nothing to do, then run the IDLE task (power saving sleep)
00264     if (runQueue == NULL)
00265         currentFiber = idle;
00266         
00267     // If the current fiber is on the run queue, round robin.
00268     else if (currentFiber->queue == &runQueue)
00269         currentFiber = currentFiber->next == NULL ? runQueue : currentFiber->next;
00270 
00271     // Otherwise, just pick the head of the run queue.
00272     else
00273         currentFiber = runQueue;
00274         
00275     // Swap to the context of the chosen fiber, and we're done.
00276     // Don't bother with the overhead of switching if there's only one fiber on the runqueue!
00277     if (currentFiber != oldFiber)        
00278         swap_context(&oldFiber->tcb, &currentFiber->tcb, oldFiber->stack_top, currentFiber->stack_top);
00279 }
00280 
00281 /**
00282   * IDLE task.
00283   * Only scheduled for execution when the runqueue is empty.
00284   * Performs a procressor sleep operation, then returns to the scheduler - most likely after a timer interrupt.
00285   */
00286 void idle_task()
00287 {
00288     while(1)
00289     {
00290         // TODO: Efficient sleep goes here. :-)
00291         //sleep();
00292         
00293         schedule();
00294     }
00295 }