/*
Copyright 2003/2004, Freie Universitaet Berlin. All rights reserved.

These sources were developed at the Freie Universität Berlin, Computer
Systems and Telematics group.

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.

- Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.
 
- Neither the name of Freie Universitaet Berlin (FUB) 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 FUB and the contributors on an "as is"
basis, without any representations or warranties of any kind, express
or implied including, but not limited to, representations or
warranties of non-infringement, merchantability or fitness for a
particular purpose. In no event shall FUB or contributors 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.

This implementation was developed by the CST group at the FUB.
Contributors: Thomas Pietsch, Bjoern Lichtblau

For documentation and questions please use the web site
http://www.scatterweb.net and the mailinglist
scatterweb@lists.spline.inf.fu-berlin.de (subscription via the Website).
Berlin, 2003/2004/2005
*/

/** \file scos.c
 ** \ingroup Firmware
 ** \brief Experimental ScatterOS.

<h3>ScatterOS</h3>

This file implements a simple cooperative scheduling mechanism which
allows to run task functions with os like blocking calls (which in
fact do not block the processor but return control to the system
and get later resumed).

The os primitives at the moment are:
<table>
<tr>
<td>::OS_yield</td>
<td>Simply returns control to the system. As this is a cooperative scheduler
long tasks or tasks which make no other OS_ calls must interrupt themself with ::OS_yield.</td></tr>
<tr><td>::OS_wait</td><td>Makes the task wait a specified amount of system ticks (may get longer if system is busy).</td></tr>
<tr><td>::OS_await</td><td>Makes the task wait for a flag set.</td></tr>
<tr><td>::OS_recv / ::OS_recvp </td><td>Makes the task wait for a packet of a given type (and a given sender if wanted). A timeout can be set and ::OS_recvp works in promiscous mode.</td>
<tr><td>::OS_send / ::OS_esend </td><td>A synchronous send, task will continue after the packet was sent or lost (removed from radio rx ringbuffer). ::OS_esend is for sending data from eeprom.</td>
</table>

These are not many but suit the needs at the moment. 

\todo OS_ calls for waiting for sensor readings and some methods for task synchronisation (binary semaphores, counting semaphores or even more?!)

Examples from scos.c:

\dontinclude scosex.c
\skip Example1:
\until Example1End

\skip Example2:
\until Example2End

\skip Example3:
\until Example3End

\skip Example4:
\until Example4End

<h3> Constraints </h3>

The goal was to write a task switching mechanism with minimal memory
requirements. Each preemptive OS requires and most cooperative OS use
one stack per task (Exceptions seen so far are PeerOS in the EYES Porject, which
preempts only lower priority tasks and lets them reside at the
stack while executing a higher priority task, and Salvo, 
which seems to implement a very similar approach).

To have a stack for each task increases memory requirements a lot, because
the size of the stack for a task is unknown and must be generously set. 
The optimum would be the maximum stack depth of the task call tree. A compiler could easily 
calculate this if recursion and function pointers are not used, but i do not know if
any compiler supports this feature. The second bad is that most times a task
won't use its maximum stack depth.

In contrast to theses approaches this mechanism uses no memory (only
some static allocated memory for task table and a little bit of stack space like
in every other function is needed). This puts some limits onto the task functions
to make this possible. 

Task functions can't and should never allocate stack space.
In fact you can allocate stack space and the scheduler will handle
it properly (that was needed for calls with long argument list which get
pushed onto the stack), but after an OS_ call the stack content will
always be undefined. 

That means that all state must be held in vars declared globally. Additionally
they should be declared volatile so the compiler won't do any optimization
on them (hold them in registers, also register content is undefined after an OS_ call).
Secondly it means that blocking OS_ function are only allowed to call within
your top-level task function, not in functions called from your top-level task function!
The reason for that is again the stack, which is undefined after an OS_ call and
so will thrash the return address for OS_ calls anywhere outside from your top-level
task function.


<h3>How it works</h3>

A task is initialized with ::startTask, which gets a pointer to the task function.
If a task can run (like a newly added task) sooner or later ::scos_call with
the id of the task in the task table and a value is called. 
::scos_call saves the current stack pointer, sets currentTask and calls the 
next-to-continue address of the task like a function with an int argument.

Then the task runs until it calls an OS_ function. 
These functions save the return address of the task on the stack as the
next-to-continue address in the task table, change the state of the task
and call ::scos_exit.

::scos_exit now just restores the stack pointer to the value ::scos_call saved
and does a return, which now is like the return of ::scos_call and so
the system is again in a clean state.
 
<h3>Related</h3>

From slau049.pdf / Page 5-2:
\code
5.1.2 The System Stack Pointer (SP)
The system stack pointer must always be aligned to even addresses because
the stack is accessed with word data during an interrupt request service. The
system SP is used by the CPU to store the return addresses of subroutine calls
and interrupts. It uses a predecrement, postincrement scheme. The
advantage of this scheme is that the item on the top of the stack is available.
The SP can be used by the user software (PUSH and POP instructions), but
the user should remember that the CPU also uses the SP. Figure 5–2 shows
the system SP bits.

From slau049.pdf / Page 5-19, Call a subroutine:
CALL dst          SP – 2 –> SP, PC+2 –> stack, dst –> PC

From slau049.pdf / Page 5-22, Return from subroutine:
RET  MOV @SP+,PC
\endcode
    
From the GCC manual:
\code
-fno-defer-pop 
Always pop the arguments to each function call as soon as that function returns. 
For machines which must pop arguments after a function call, the compiler normally 
lets arguments accumulate on the stack for several function calls and pops them all at once. 
\endcode
 
Perhaps a cleaner and more portable but also more memory consuming
implementation would be possible with setjmp()/longjmp() macros, see 
- http://publications.gbdirect.co.uk/c_book/chapter9/nonlocal_jumps.html
- http://www.csl.mtu.edu/cs4411.ck/www/NOTES/non-local-goto/mtp.h


Other OS for MSP430:

- <a href="http://www.tinyos.net/">TinyOS</a>
- <a href="">Salvo</a>
- PeerOS
- <a href="http://users.ints.net/skidan/SOS/">SOS</a>
- <a href="www.freertos.org">FreeRTOS</a>
- <a href="http://mantis.cs.colorado.edu/index.php/tiki-index.php">MANTIS </a>
- <a href="http://www.sics.se/~adam/contiki/">Contiki</a>

**/

#include "ScatterWeb.System.h"
////////////////////////////////////////////////////////////////////////////////
/// \name Possible values for task states (Task.state)
//@{
#define T_DESTROYED   (0)       ///< Initial state of whole task table and after return of a task, task is not valid!
#define T_ELIGIBLE    (1)       ///< Task is eligible to run. Initial state after adding a new task, a ::scos_yield or an expired ::scos_wait.
#define T_WAITING     (2)       ///< Task is waiting for a timeout with a scos_wait.
#define T_RECV        (3)       ///< Task is waiting for a packet.
#define T_RECVP       (4)       ///< Task is waiting for a packet in promiscous mode.
#define T_SEND        (5)       ///< Task is sending a packet blocking.
#define T_AWAIT       (6)       ///< Task is awaiting a specific state.
#define T_TRECV       (7)       ///< Task is waiting for a packet with timeout.
#define T_TRECVP      (8)

//@}

////////////////////////////////////////////////////////////////////////////////
/// \name Task table & Other vars
//@{

typedef struct {
  UINT16 address;   ///< Next address to continue for this task, initialized with function address of a new task.
  UINT16 stackSize;
  UINT16 state;     ///< Current state of the task.
  union {
    struct {
      UINT16 type;
      UINT16 sender;
    } RECV;
    
    struct {
      UINT8* adr;
      UINT8 value;
    } AWAIT;
  };
} Task; ///< Task table struct.

volatile Task Tasks[MAX_TASKS];    ///< Task table.
volatile UINT16 nextTask;    ///< Used by scos_heartbeat to go round robin over all tasks (except sending & receiving).
volatile UINT16 currentTask; ///< Always set to currentTask by ::scos_call.
volatile UINT16 savedSP;     ///< Saved stack pointer in ::scos_call.
volatile UINT16 Threading_currentThread;

COMMAND(sco, SERIALONLY){
  UINT16 i;
  Comm_print("Nr\tAdr\tState\tStack\r\n");
  for(i=0; i<MAX_TASKS; i++){
    if(Tasks[i].address != 0) Comm_print("%i\t%x\t%i\t%i\r\n", i, Tasks[i].address, Tasks[i].state, Tasks[i].stackSize);
    else                      Comm_print("%i\t ---\r\n", i);
  }
}
//@}

////////////////////////////////////////////////////////////////////////////////
/// \name SCOS and Task initialization.
//@{

/// Clear task table and variables.
bool Threading_init(){
  UINT16 i;
  for(i=0; i<MAX_TASKS; i++){
    Tasks[i].address = 0x0000;
    Tasks[i].state = T_DESTROYED;
    Tasks[i].stackSize = 0;
  }
  currentTask = 0;
  nextTask = 0;
  savedSP = 0;
  return True;
}

/// Starts a task.
bool Threading_add(void* address){
    UINT16 i;
    for(i=0; i<MAX_TASKS; i++) if(Tasks[i].state == T_DESTROYED) break;
    if(i<MAX_TASKS){ // found an empty place
      Tasks[i].address = (UINT16) address;
      Tasks[i].state = T_ELIGIBLE;
      Tasks[i].stackSize = 0;
      runModule |= MF_SCOS;
      return True;
    }
    else return False; 
}

//@}

////////////////////////////////////////////////////////////////////////////////
/// \name The tricky part of the OS
//@{
#define NAKEDFUNC __attribute__((naked))

NAKEDFUNC void scos_prolog(UINT16 value, UINT16 address, UINT16 stackoffset){
  // Subtract stack space of the task from the stack.
  __asm__ __volatile__("sub %0, r1":: "r" (stackoffset));
  // Fake set return value for function, not needed as value lands in here on r15 as first argument.
  //__asm__ __volatile__("mov %0, r15":: "r" (value): "r15");
  // Now do a branch to that location
  __asm__ __volatile__("br %0":: "r" (address)); // save stack pointer  
}

/** Helper for scos_call. 
   Had to be put into an extra functions because of following problem:

   The following instruction ("mov &savedSP, r1"::) is not really needed because if execution
   returns here, the stack poitner should be what we saved before. The
   important thing is to tell the compiler, that the usually caller preserved
   registers (r6-r11) may have changed!
   The problem is the indexing into the Tasks table. If following line is omitted the
   assembler output is:
   
 scos_prolog(value, Tasks[currentTask].address, Tasks[currentTask].stackSize);
    7154:	1e 42 50 06 	mov	&0x0650,r14	;0x0650
    7158:	3b 40 54 06 	mov	#1620,	r11	;#0x0654
...
    718a:	b0 12 42 71 	call	#28994		;#0x7142
  //__asm__ __volatile__("mov &savedSP, r1"::); // restore stack pointer
  Tasks[currentTask].address = 0x0000;
    718e:	1e 42 50 06 	mov	&0x0650,r14	;0x0650
...
    71a0:	0f 5b       	add	r11,	r15	;
    71a2:	8f 43 00 00 	mov	#0,	0(r15)	;r3 As==00
  Tasks[currentTask].state = T_DESTROYED;
...
    71b8:	0f 5b       	add	r11,	r15	;
    71ba:	8f 43 04 00 	mov	#0,	4(r15)	;r3 As==00
   
   That is bad. At the beginning the base address of Tasks is moved into r11
   for reading out of the table for the scos_prolog call. 
   r11 is later (after scos_prolog call) used to index into Tasks again, 
   and the compiler can assume, that r11 did not change (according to normal 
   calling conventions), but that may be wrong in this case.
   
   When the following instruction is used, the compiler omits the "add r11,r15"
   and addresses the table directly:
     __asm__ __volatile__("mov &savedSP, r1"::); // restore stack pointer
    718e:	11 42 4a 06 	mov	&0x064a,r1	;0x064a
  Tasks[currentTask].address = 0x0000;
...
    71a4:	8f 43 54 06 	mov	#0,	1620(r15);r3 As==00
  Tasks[currentTask].state = T_DESTROYED;
...
    71ba:	8f 43 58 06 	mov	#0,	1624(r15);r3 As==00
    
    I dont know why the compiler does that thing not always this way (it
    saves on instruction). I tried to force it by telling all registers get
    clobbered through this instruction:
   __asm__ __volatile__("mov &savedSP, r1":: : "r15", "r14", "r13", "r12", "r11", "r10", "r9", "r8", "r7", "r6"); // restore stack pointer
    
    But this produced the same behaviour like the first, BUT instead of r11 being used
    it is now r5 which is even more worse. r5 is the frame pointer and strangely used
    by gcc. The compiler should never assume r5 is preserved over function calls,
    very strange why it does that here (even when r15 is appended to the list of clobbered 
    registers).
    
    Anyway it works with the second. But that may change with -O flags or anything
    else, so best will be to put that into an extra function. <=== DONE
    
    Make sure this function does not get inlined into scos_call again with 
    -fno-inline for this file ?! 
*/
void _destroy_task(){
  Tasks[currentTask].address = 0x0000;
  Tasks[currentTask].state = T_DESTROYED;
  savedSP = 0;  // clear saved stack pointer
}

// This is the entry call for calling a task address.
NAKEDFUNC void scos_call(UINT16 task, UINT16 value){
  __asm__ __volatile__("mov r1, &savedSP"::: "memory"); // save stack pointer
  currentTask = task;
  Threading_currentThread = task;
  scos_prolog(value, Tasks[currentTask].address, Tasks[currentTask].stackSize);
  // If this call returns to the scheduler this task has ended with a return.
  _destroy_task();
  __asm__ __volatile__("ret"::);
}

// This is the exit from OS functions. It restores SP so that the ret is like
// the return in scos_call and everything is clean after running.
NAKEDFUNC void scos_return(void){
  __asm__ __volatile__("mov &savedSP, r1"::); // restore stack pointer
  savedSP = 0;  // clear saved stack pointer
  __asm__ __volatile__("ret"::);              // Looks now like the return in scos_call.
}

/** Macro for OS_* functions called from a task. This is the same for every function.
 * It first checks the Stack depth since saving the SP with scos_call, which must be 4 due to the
 * 2 calls from scos_call and the task itself. 
 * 
  if(savedSP - frame_adr != 4){ \
      print("Task %i Stack error, savedSP: %x frame_adr: %x\r\n", currentTask, savedSP, frame_adr); \
      Tasks[currentTask].state = T_DESTROYED; \
      scos_return(); \
  } \
  
 *    
 **/  
#define UPDATE_TT(newstate) \
  if(savedSP==0){ \
    Comm_print("Invalied call to OS_* function from %x\r\n", (*(((UINT16*)frame_adr))) - 4); \
    return 0; \
  } \
  Tasks[currentTask].address = *(((UINT16*)frame_adr)); \
  Tasks[currentTask].state = newstate; \
  Tasks[currentTask].stackSize = (savedSP - frame_adr) - 4;

//@}

/// The scheduling function. Looks through the table for next T_ELIGIBLE task and calls it.
bool Threading_eventHandler(){
  UINT16 i;
  // search from nextTask+1 to end.
  for(i=nextTask+1; i<MAX_TASKS; i++){
    if(Tasks[i].state == T_ELIGIBLE ||
       (Tasks[i].state == T_AWAIT && (*(Tasks[i].AWAIT.adr) == Tasks[i].AWAIT.value))
    ){
      nextTask = i;
      goto found;
    }
  }
  // search from 0 to nextTask
  for(i=0; i<=nextTask; i++){
    if(Tasks[i].state == T_ELIGIBLE ||
       (Tasks[i].state == T_AWAIT && (*(Tasks[i].AWAIT.adr) == Tasks[i].AWAIT.value))
    ){
      nextTask = i;
      goto found;
    }
  }
  goto exit;  // If none was found exit routine.
  // Execute at given addres of the task. Casting that address to
  // a function with an uint argument does imitate a return value
  // of tasks previous call to a scos_ function.
  found:  
  scos_call(nextTask, 1); 
  return True;  
  exit:   
  runModule &= ~ MF_SCOS;
  return True;
}

////////////////////////////////////////////////////////////////////////////////
/// \name Task functions: Yield.
//@{
bool Threading_doEvents(){
  UINT16 frame_adr = GET_FRAME_ADDR(Threading_doEvents);
  UPDATE_TT(T_ELIGIBLE);   // Nothing more to do here, Tasks stays T_ELIGIBLE.
  runModule |= MF_SCOS;
  scos_return();
  return False;
}
//@}

////////////////////////////////////////////////////////////////////////////////
/// \name Task functions: Wait.
//@{
void _scos_wait_timeout(UINT16 data){
  Tasks[data].state = T_ELIGIBLE;
  runModule |= MF_SCOS;
}

bool Threading_sleep(UINT16 ticks){
  UINT16 frame_adr = GET_FRAME_ADDR(Threading_sleep);
  UPDATE_TT(T_WAITING);
  Timers_add(ticks, _scos_wait_timeout, currentTask);
  scos_return();
  return False;
}
//@}

////////////////////////////////////////////////////////////////////////////////
/// \name Task functions: Await.
/// \todo Rewrite for sleep scheme.
//@{
bool Threading_wait(UINT8* adr, UINT8 value){
  UINT16 frame_adr = GET_FRAME_ADDR(Threading_wait);
  UPDATE_TT(T_AWAIT);
  Tasks[currentTask].AWAIT.adr = (UINT8*) adr;
  Tasks[currentTask].AWAIT.value = value;
  scos_return();
  return False;
}
//@}

////////////////////////////////////////////////////////////////////////////////
/// \name Task functions: Receive.
//@{
void _scos_recv_timeout(UINT16 data){
  scos_call(data, 0);    
}

bool Threading_packetHandler(){
  UINT16 i;
  if(rxPacket.to != Configuration.id){
    for(i=0; i<MAX_TASKS; i++){
        if(Tasks[i].state == T_RECVP || Tasks[i].state == T_TRECVP){
          if(Tasks[i].RECV.type == rxPacket.type && (Tasks[i].RECV.sender == 0xFFFF || Tasks[i].RECV.sender == rxPacket.from)){
            if(Tasks[i].state == T_TRECVP) Timers_remove(_scos_recv_timeout, i);
            scos_call(i, 1);
            return True;
          }    
        }
    }  
  }
  else {
    for(i=0; i<MAX_TASKS; i++){
      if(Tasks[i].state == T_RECV || Tasks[i].state == T_TRECV || Tasks[i].state == T_RECVP || Tasks[i].state == T_TRECVP){
        if(Tasks[i].RECV.type == rxPacket.type && (Tasks[i].RECV.sender == 0xFFFF || Tasks[i].RECV.sender == rxPacket.from)){
          if(Tasks[i].state == T_TRECV || Tasks[i].state == T_TRECVP) Timers_remove(_scos_recv_timeout, i);
          scos_call(i, 1);
          return True;
        }
      }
    } 
  }
  return False;
}

bool Threading_recv(UINT16 sender, UINT16 type, UINT16 timeout){
  UINT16 frame_adr = GET_FRAME_ADDR(Threading_recv);
  UPDATE_TT(T_RECV);
  Tasks[currentTask].RECV.sender = sender;
  Tasks[currentTask].RECV.type = type;
  if(timeout != 0){
    Tasks[currentTask].state = T_TRECV;
    Timers_add(timeout, _scos_recv_timeout, currentTask);
  }
  scos_return();
  return False;
}

bool Threading_recvp(UINT16 sender, UINT16 type, UINT16 timeout){
  UINT16 frame_adr = GET_FRAME_ADDR(Threading_recvp);
  UPDATE_TT(T_RECVP);
  Tasks[currentTask].RECV.sender = sender;
  Tasks[currentTask].RECV.type = type;
  if(timeout != 0){
    Tasks[currentTask].state = T_TRECVP;
    Timers_add(timeout, _scos_recv_timeout, currentTask);
  }
  scos_return();
  return False;
}

//@}

////////////////////////////////////////////////////////////////////////////////
/// \name Task functions: Send. TODO
//@{
bool Threading_sentPacketHandler(UINT16 pid, UINT16 success){
  scos_call(pid-1, success);
  return True;
}

bool Threading_send(UINT16 to, UINT16 type, UINT8*h, UINT16 hl, UINT8* d, UINT16 dl){
  UINT16 frame_adr = GET_FRAME_ADDR(Threading_send);
  packet_t packet;
  UPDATE_TT(T_SEND);
  packet.to = to;
  packet.type = type;
  packet.header = h;
  packet.header_length = hl;
  packet.data = d;
  packet.data_length = dl;
  Net_send(&packet, (fp_char_t) currentTask+1); // todo return if not possible
  scos_return();
  return False;
}

bool Threading_esend(UINT16 to, UINT16 type, UINT8*h, UINT16 hl, UINT16 d, UINT16 dl){
  UINT16 frame_adr = GET_FRAME_ADDR(Threading_esend);
  packet_t packet;
  UPDATE_TT(T_SEND);
  packet.to = to;
  packet.type = type;
  packet.header = h;
  packet.header_length = hl;
  packet.data = (UINT8*)d;
  packet.data_length = dl;
  Net_esend(&packet, (fp_char_t) currentTask+1); // todo return if not possible
  scos_return();
  return False;
}
//@}
