Simple RTOS for Microchip Baseline and Midrange MCUs

by Isaac Marino Bavaresco

//==============================================================================
// SimpleRTOS - Very simple RTOS for Microchip(R) Baseline and Midrange uCs
// v1.00 (2008-09-23)
// isaacbavaresco@yahoo.com.br
//==============================================================================
/*
 Copyright (c) 2007-2008, Isaac Marino Bavaresco
 All rights reserved.

 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions are met:
     * Redistributions of source code must retain the above copyright
       notice, this list of conditions and the following disclaimer.
     * Neither the name of the author nor the
       names of its contributors may be used to endorse or promote products
       derived from this software without specific prior written permission.

 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ''AS IS'' AND ANY
 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
//==============================================================================
/*
    Notes:  - Works with Hi-Tech PICC v9.60PL2;

            - Assembler optimizations must be OFF for every file that implements
              task functions (it is better to have the task functions in one or
              more files with no standard functions, to minimize the un-optimized
              code length).

            - Every task function must have a call to the macro
              "TASK_INIT( <task function name> );" as the first statement;

            - Every function called directly or indirectly by more than one task
              must have a call to the macro "FUNC_INIT( <function name> );" as the
              first statement, unless it doesn't have any parameters nor automatic
              variables, or all paths through the call-graphs that it belongs have
              at least one function that calls "FUNC_INIT" before the function is
              called.

              Unfortunately this impose certain restrictions when using library
              functions, unless each library function is called from just one
              task, or it is present only in call-graphs that at least one
              function calls "FUNC_INIT" before the library function is called,
              or you rebuild the library adding the call to "FUNC_INIT" to the
              library functions that need it.

            - SimpleRTOS functions and macros that may cause a context switch
              (Eg: Yield, Sleep, DeleteTask (when deleting itself) and
              MutexTake ) must be called only directly inside the task function,
              never indirectly by other functions.


    TO DO:  - Find a way to reuse local variables of tasks that are never active
              at the same time.

            - Implement semaphores.

            - Implement priorities and slice length.

*/
//==============================================================================
#include <pic.h>
#include <stdlib.h>
#include "SimpleRTOS.h"
//==============================================================================

// Points to the context of the current task.
TS_Context  *CurrentTask        = NULL;

// Points to the head of the unused contexts list. This list is organized as a
// single-linked linear list.
TS_Context  *bank2 FreeContexts = NULL;

// Points to the head of the running tasks contexts list. This list is organized
// as a double-linked circular list.
TS_Context  *bank2 RunningTasks = NULL;

// Points to the head of the delayed tasks contexts list. This list is organized
// as a double-linked linear list.
TS_Context  *bank2 DelayedTasks = NULL;
//==============================================================================
// Tick counter, counts to 255 and roll-over to zero.
unsigned char   Ticks;

// Temporary storage for PCH during the context switching.
unsigned char   SavePCH;
// Temporary storage for PCL during the context switching.
unsigned char   SavePCL;
// Temporary storage for FSR during the context switching.
unsigned char   SaveFSR;
// Temporary storage for PCLATH during the context switching.
unsigned char   SavePCLATH;

// Signals that the running tasks contexts list was already changed by a Sleep.
bit             AlreadySwitched     = 0;
//==============================================================================
// Removes a task from any double-linked list.
void RemoveTaskFromList( TS_Context *Task )
    {
    TS_Context  * bank2 *List;
    TS_Context  *Previous, *Next;

    // Make 'List' point to the pointer to the head of the list.
    List            = Task->List;

    // Mark the task as not belonging to any list.
    Task->List      = NULL;

    // Make 'Previous' point to the task that precedes this one in the list (if any).
    Previous        = Task->Previous;

    // Un-link the task from the list.
    Task->Previous  = NULL;

    // Make 'Next' point to the task that follows this one in the list (if any).
    Next            = Task->Next;

    // Un-link the task from the list.
    Task->Next      = NULL;

    // The task is the last one in a circular list...
    if( Previous == Task )
        {
        // ... just remove it from the list.
        *List       = NULL;
        // Finished
        return;
        }

    // The task is the head of the list
    if( *List == Task )
        // Make the next task (if any) be the head of the list.
        *List   = Next;

    // If there is a previous task...
    if( Previous != NULL )
        // ... make it point to the task that follows this one in the list (if any).
        Previous->Next  = Next;

    // If there is a next task...
    if( Next != NULL )
        // ... make it point to the task that precedes this one in the list (if any).
        Next->Previous  = Previous;
    }
//==============================================================================
// If we are not using mutexes or semaphores, we don't need the following function
#if         defined USE_BLOCKINGS

void RemoveTaskFromDelayList( TS_Context *Task )
    {
    TS_Context  *PreviousDelayedTask, *NextDelayedTask;

    PreviousDelayedTask = Task->PreviousDelayedTask;
    NextDelayedTask     = Task->NextDelayedTask;

    // If this task is the first one in the list of delayed tasks...
    if( PreviousDelayedTask == NULL )
        // ... make the next task in the list (if any) be the first.
        DelayedTasks    = NextDelayedTask;
    else
        // ... else make the task before this one in the list point to the task following this one (if any).
        PreviousDelayedTask->NextDelayedTask    = NextDelayedTask;

    // If there is a task after this one in the list...
    if( NextDelayedTask != NULL )
        // ... make it point to the task before this one in the list (if any).
        NextDelayedTask->PreviousDelayedTask    = PreviousDelayedTask;

    // Mark this task as not having a previous one in the delayed tasks list.
    Task->PreviousDelayedTask   = NULL;
    // Mark this task as not having a next one in the delayed tasks list.
    Task->NextDelayedTask       = NULL;
    // Mark this task as not belonging to the delayed tasks list.
    Task->DelayList             = NULL;
    }

#endif  //  defined USE_BLOCKINGS
//==============================================================================
void InsertTaskInCircularList( TS_Context *Task, TS_Context * bank2 *List )
    {
    TS_Context *First, *Last;

    // Mark the task as belonging to the list.
    Task->List  = List;

    // The list is empty...
    if( *List == NULL )
        {
        // ... insert the task into the list.
        *List           = Task;
        // The list is circular, the task is the previous of itself.
        Task->Previous  = Task;
        // The list is circular, the task is the next of itself.
        Task->Next      = Task;
        }
    else
        {
        // Make 'First' point to the first element in the list.
        First           = *List;
        // The last element of a circular list is the element before the first.
        Last            = First->Previous;
        // We are inserting at the end, this element becomes the last one.
        First->Previous = Task;
        Task->Next      = First;
        Last->Next      = Task;
        Task->Previous  = Last;
        }
    }
//==============================================================================
void InsertTaskInDelayList( TS_Context *Task, unsigned char Time )
    {
    TS_Context *p, *q, *Next;
    unsigned char t;

    // Set the new task's time to wake.
    Task->TDelay    = Time;
    // Make the new task belong to the delayed tasks list.
    Task->DelayList = &DelayedTasks;

    // The list is empty...
    if( DelayedTasks == NULL )
        {
        // ... just insert the task into the list.
        DelayedTasks                = Task;
        // The list is linear, there is no previous task.
        Task->PreviousDelayedTask   = NULL;
        // The list is linear, there is no next task.
        Task->NextDelayedTask       = NULL;
        }
    // The list is not empty...
    else
        {
        // ... make 'p' point to the first element.
        p = DelayedTasks;
        // Get the first element's time to wake.
        t = p->TDelay;
        // The time to wake of the new task is less than the first element's...
        if( (unsigned char)(Time - t) > 0x7f )
            {
            // ... insert the task as the first element.
            DelayedTasks                = Task;
            // The task is now the first element, there is no previous one.
            Task->PreviousDelayedTask   = NULL;
            // The former first element is now the next one of this task.
            Task->NextDelayedTask       = p;
            // This task is now the previous one of the former first element.
            p->PreviousDelayedTask      = Task;
            }
        // We need to find where the task is to be inserted...
        else
            {
            // ... iterate through the remainig elements of the list (if any).
            for( q = p->NextDelayedTask; q != NULL; q = q->NextDelayedTask )
                {
                // Get the time to wake of the task pointed to by 'q'.
                t = q->TDelay;
                // The time to wake of the new task if less than the one pointed to by 'q'...
                if( (unsigned char)(Time - t) >= 0x7f )
                    // ... stop.
                    break;
                // Advance one element.
                p = q;
                }
            // We are inserting after the element pointed to by 'p'.
            Next                        = p->NextDelayedTask;
            Task->PreviousDelayedTask   = p;
            Task->NextDelayedTask       = Next;
            p->NextDelayedTask          = Task;
            // There is a next element...
            if( Next != NULL )
                // ... make it point to the new task.
                Next->PreviousDelayedTask   = Task;
            }
        }
    }
//==============================================================================
// Test to see if it's time to wake the first delayed task.
void CheckDelayList( void )
    {
    TS_Context *p;
    unsigned char t;

    // The delayed tasks list is not empty...
    if(( p = DelayedTasks ) != NULL )
        {
        // Get the first element's time to wake.
        t = DelayedTasks->TDelay;
        // It's time to wake the task...
        if( (signed char)(t - Ticks) <= 0 )
        {
#if         defined USE_BLOCKINGS

            // Remove the task from the dalayed task list.
            RemoveTaskFromDelayList( p );
            // The task was delayed because it was waiting for some event...
            if( p->List != NULL )

#endif  //   defined USE_BLOCKINGS

                // .. remove the task from the event's list.
                RemoveTaskFromList( p );

            // Insert the task at the end of the running tasks list.
            InsertTaskInCircularList( p, &RunningTasks );
            }
        }
    }
//==============================================================================
void _Sleep( unsigned char t )
    {
    // Needed because this function will (or may) be called by more than one task.
    FUNC_INIT( _Sleep );

    // Remove the task from the running tasks list.
    RemoveTaskFromList( CurrentTask );
    // Flag that the running tasks list alread changed.
    AlreadySwitched = 1;
    // The sleep time is less than the maximum...
    if( t < 128 )
        {
        // ... Set the task's time to wake.
        CurrentTask->TDelay = Ticks + t;
        // Insert the task into the delayed tasks list.
        InsertTaskInDelayList( CurrentTask, Ticks + t );
        }

/*    // This may be useful in the future, but is pointless now.
    // The task is being suspended for undeterminated time...
    else
        // ... insert the task into the suspended tasks list.
        InsertTaskInCircularList( CurrentTask, &SuspendedTasks );
*/
    }
//==============================================================================
bit ResumeTask( TS_Context *Task )
    {
    // Needed because this function will (or may) be called by more than one task.
    FUNC_INIT( ResumeTask );

#if         defined USE_BLOCKINGS

    if( Task == NULL || Task->DelayList != &DelayedTasks )
        return 0;

    RemoveTaskFromDelayList( Task );

    if( Task->List != NULL )
    RemoveTaskFromList( Task );

#else   //  defined USE_BLOCKINGS

    if( Task == NULL || Task->List != &DelayedTasks )
    return 0;

    RemoveTaskFromList( Task );

#endif  //  defined USE_BLOCKINGS

    InsertTaskInCircularList( Task, &RunningTasks );

    return 1;
    }
//==============================================================================
void Scheduler( void )
    {
    // Needed because this function will be called by more than one task.
    FUNC_INIT( Scheduler );
    //--------------------------------------------------------------------------
    // Save the current context
    //--------------------------------------------------------------------------

    // Save current's task FSR before we change it.
    SaveFSR     = FSR;

    // All task control structures are in banks 2 and 3.
    IRP         = 1;
    // Make FSR point to the current task's context.
    FSR         = (ptrdiff_t)CurrentTask;

    // Save the current task's resume address (high byte) into the task's context.
    INDF        = SavePCH;
    FSR++;

    // Save the current task's resume address (low byte) into the task's context.
    INDF        = SavePCL;
    FSR++;

    // Save the current task's PCLATH into the task's context.
    INDF        = SavePCLATH;
    FSR++;

    // Save the current task's FSR into the task's context.
    INDF        = SaveFSR;

    // Make PCLATH point to the current page
    asm( "movlw high ($+2)          " );
    asm( "movwf 10                  " );    // PCLATH

    asm( "global _AbortTask" );
    // Execution will begin here if a task deletes itself.
    asm( "_AbortTask:" );

    //----------------------------------------------------------------------
    // Switch context
    //----------------------------------------------------------------------

    // Stay here while there is no task ready to run.
    do
        CheckDelayList();
    while( RunningTasks == NULL );

    // The previous task itself didn't changed the running tasks list...
    if( !AlreadySwitched )
        // ... switch the task.
        RunningTasks = RunningTasks->Next;
    AlreadySwitched = 0;

    // Make 'CurrentTask' point to the current task's  context.
    CurrentTask = RunningTasks;

    //----------------------------------------------------------------------
    // Restore context
    //----------------------------------------------------------------------

    // Obtain address of current context
    IRP         = 1;
    FSR         = (ptrdiff_t)CurrentTask;

    // Copy "PCH" from the context to PCLATH
    PCLATH      = INDF;
    FSR++;

    SavePCL     = INDF;
    FSR++;

    SavePCLATH  = INDF;
    FSR++;

    // Copy "FSR" from context
    FSR         = INDF;

    // Copy SavePCL to PCL (effectively jumps to the task's resume address).
    PCL         = SavePCL;
    }
//==============================================================================
void ContextInit( TS_Context *Context, void(*TaskFunc)(void) )
    {
    Context->PCH                        = (unsigned int)TaskFunc >> 8;
    Context->PCL                        = (unsigned int)TaskFunc;
    Context->PCLATH                     = (unsigned int)TaskFunc >> 8;
    Context->FSR                        = 0;
    Context->TDelay                     = 0;
    #ifdef      USE_BLOCKINGS
        Context->PreviousDelayedTask    = 0;
        Context->NextDelayedTask        = 0;
        Context->DelayList              = 0;
    #endif  //  USE_BLOCKINGS
    #ifdef      USE_SLICE_LENGTH
        Context->SliceLength            = 0;
    #endif  //  USE_SLICE_LENGTH

    #ifdef      USE_PRIORITIES
        Context->Priority               = 0;
    #endif  //  USE_PRIORITIES
    Context->Previous                   = 0;
    Context->Next                       = 0;
    Context->List                       = 0;
    }
//==============================================================================
void _StartRTOS( void )
    {
    CurrentTask = RunningTasks;

    // Obtain address of current context
    IRP         = 1;
    FSR         = (ptrdiff_t)CurrentTask;

    // Copy "PCH" from context to PCLATH
    PCLATH      = INDF;
    FSR++;

    SavePCL     = INDF;
    FSR++;

    SavePCLATH  = INDF;
    FSR++;



    // Copy "FSR" from context
    FSR         = INDF;

    Ticks       = 0;

    // Copy SavePCL to PCL (effectively jumps to the task's start address).
    PCL         = SavePCL;
    }
//==============================================================================
TS_Context *CreateTask( void(*TaskFunc)(void) )
    {
    TS_Context  *p;

    // Needed because this function will (or may) be called by more than one task.
    FUNC_INIT( CreateTask );

    // There is no free context to be used...
    if( FreeContexts == NULL )
        // ... return failure.
        return NULL;

    // Make 'p' point to the first free context.
    p   = FreeContexts;
    // Remove the context from the free list.
    FreeContexts    = FreeContexts->Next;

    // Initializes the context with the new task's address.
    ContextInit( p, TaskFunc );

    // Insert the new task into the running tasks list.
    InsertTaskInCircularList( p, &RunningTasks );

    // Return the address of the new task's context.
    return p;
    }
//==============================================================================
bit _DeleteTask( TS_Context *Task )
    {
    // Needed because this function will (or may) be called by more than one task.
    FUNC_INIT( _DeleteTask );

    // The task is invalid or already deleted...
    if( Task == NULL || Task->List == &FreeContexts )
        // ... finish.
        return 0;

#if         defined USE_BLOCKINGS

    // The task is delayed...
    if( Task->DelayList == &DelayedTasks )
        // ... remove it from the delayed tasks list.
        RemoveTaskFromDelayList( Task );

#endif  //  defined USE_BLOCKINGS

    // The task is waiting for some event...
    if( Task->List != NULL )
        // ... remove it from the event list.
        RemoveTaskFromList( Task );

    // Link the task's context to the free contexts list
    Task->Next      = FreeContexts;
    FreeContexts    = Task;
    // Mark the context as belonging to the free contexts list.
    Task->List      = &FreeContexts;

    // The task is deleting itself...
    if( Task == CurrentTask )
        // ... return a status saying that the task MUST terminate.
        return 1;
    // The task is not deleting itself...
    else
        // ... return a status saying that the task should continue.
        return 0;
    }
//==============================================================================
void InitRTOS( TS_Context *Contexts, unsigned char Number )
    {
    unsigned char i;

    // No contexts to be initialized... The RTOS is useless.
    if( Contexts == NULL || Number == 0 )
    {
        FreeContexts        = NULL;
        return;
        }

    // Initialize all contexts and link them to the free contexts list.
    FreeContexts            = Contexts;
    for( i = 0; i < Number - 1; i++ )
        {
        Contexts[i].Next    = &Contexts[i+1];
        Contexts[i].List    = &FreeContexts;
        }
    Contexts[i].Next    = NULL;
    Contexts[i].List    = &FreeContexts;
    }
//==============================================================================
bit _MutexTake( TS_Mutex *Mutex, unsigned char t )
    {
    // Needed because this function will (or may) be called by more than one task.
    FUNC_INIT( _MutexTake );

    // The mutex has no owner or is already owned by the current task...
    if( Mutex->Owner == NULL || Mutex->Owner == CurrentTask )
        {
        // ... make the current task the owner of the mutex.
        Mutex->Owner    = CurrentTask;
        // Return a status saying that the task doesn't have to yield.
        return 1;
        }
    // The mutex has a owner already and the task is willing to wait...
    else if( t != 0 )
        {
        // ... delay or suspend the task (depending on the value of 't').
        _Sleep( t );
        // Insert te task into the mutex's event list.
        InsertTaskInCircularList( CurrentTask, &Mutex->WaitingList );
        // Return a status saying that te task MUST yield.
        return 0;
        }
    // Return a status saying that the task doesn't have to yield
    // (but it needs to check if it really got the mutex).
    return 1;
    }
//==============================================================================
bit MutexGive( TS_Mutex *Mutex )
    {
    TS_Context *p;

    // Needed because this function will (or may) be called by more than one task.
    FUNC_INIT( MutexGive );

    // The current task doesn't own the mutex...
    if( Mutex->Owner != CurrentTask )
        // ... return failure.
        return 0;

    // There are tasks waiting for the mutex...

    if(( p = Mutex->WaitingList ) != NULL )
        {
        // ... remove the first task from the mutex's event list.
        RemoveTaskFromList( p );
        // The task is in the delayed tasks list also...
        if( p->DelayList == &DelayedTasks )
            // ... remove it.
            RemoveTaskFromDelayList( p );
        // Insert the task into the running tasks list.
        InsertTaskInCircularList( p, &RunningTasks );
        // The task is now the owner of the mutex.
        Mutex->Owner    = p;
        }
    // There are no tasks waiting for the mutex...
    else
        // ... mark the mutex as having no owner.
        Mutex->Owner    = NULL;

    return 1;
    }
//==============================================================================