Wednesday, June 6, 2012

A new weapon in the war against Bugs and Photino Birds

Keil μVision 4 Debugger/Simulator. This is a small part of the larger (450MB, really guys?) μVision suite, but the only part I care about. With it I was able to debug my Task code, which is interesting given that I did not write or compile my code in μVision. Get the program and install it (it installs fine under Wine on Linux) and then bring up any example project, compile it, and get into debug mode. Then, right-click the disassembly window and select "Load Hex or Object File...". Now select the master .elf file that was compiled with GnuARM. It will load, and the simulated processor will be reset, so it starts at location 0 (of your code, apparently it skips the ISP).

And now for a word (or thousand) about tasks...

I like to proclaim that operating systems are for wimps (when it comes to embedded systems) but it looks more and more like I am writing such a system. This week I introduced the concept of Tasks. I stole the concept from reading about the Apollo Guidance Computer, but apparently this is still a real-time OS concept.

A Task is a chunk of code that has two properties:
  • It is short
  • It is to be kicked off a certain definite time in the future
For instance: The BMP180 baro/temperature sensor is commanded to take a measurement. It requires a finite time (~5-25 milliseconds, but calculable in advance to 1 millisecond precision) to take the measurement, and then is read out over I2C. This is way too long to be busy waiting, so we command a measurement now, then set up a task to read it later.

Tasks can do any short task, and by short I mean considerably shorter than a millisecond. Periodic tasks are handled by the task itself scheduling another execution of itself some constant finite time in the future.

In this implementation, a task is specified by a function pointer, a void "stuff" pointer, and a time until kickoff. The function pointer points to a function that takes a void pointerand returns nothing. The void pointer can point to anything you want, or even be just a number cast to pointer type, but is typically a pointer to an object, you cast it to the right class inside your code. This way you can call an object's methods in a task.

typedef void (*taskfunc)(void*);

What makes tasks different from other interrupt handlers is that a task is scheduled, and an interrupt can be based on an unscheduled unpredictable event. So, to set up a task, you need a time to execute it, while to set up an interrupt, you don't. It happens that tasks are based on interrupts in this implementation, but that is a design choice of me and the designers of the LPC.

However, since task scheduling is based on interrupts, tasks run in the IRQ state. The most important thing about this is that all further interrupts are delayed until after this task is finished.

An aside: The LPC user manual refers to these delayed interrupts as "disabled" interrupts. Interrupts which are ignored and never followed are "masked".

The task scheduler works with an array of task descriptors, structures which hold the task function pointer, stuff pointer, time between tasks, and index of the next task descriptor.

The task manager is driven off of LPC2148 timer 0. This timer has four match registers. One is used to match and reset at 60M cycles, so that the timer subdivides a second. One is set to issue an interrupt when it matches, and this is used to drive the task manager. Because of the 1 second limit, no task can be scheduled more than 1 second in the future.

The task manager contains two main blocks of code, the scheduler and the interrupt handler. The scheduler is the external interface by which external code sets up a task to be run a certain time in the future. The interrupt handler uses the timer and its interrupts to make the tasks happen as scheduled. Both pieces of code use the task list data to do their jobs. There is also a task list init function which sets up the interrupt handler and initializes and starts timer 0.

The task list is an array of objects of class Task. In order to make insertions and deletions easy, we treat this array as a linked list, but the link is an array index rather than a pointer. We keep a head index which points at the taks which will be executed when the timer interrupt fires next. Each Task contains a pointer to the Task to be
executed next after it, and the time in ticks that this task is to be run after the previous task is kicked off. This is all set up to make the interrupt handler simple at the expense of making the scheduler hard.

class Task {
  Task(const Task&);
  taskfunc f; //code for this task
  void* p;    //pointer to stuff to pass to this task
  int next;   //array index of task after this,
              //or -1 if this is the end of the list
  int ticks;  //What to add to the timer match register when this task
              //comes to the front of the line, or -1 if the task is erased

class TaskManager {
    static const int tasklist_size=10;
    int head;
    Task tasklist[tasklist_size];
    static void handleTimerISR();
    int scheduleCore(int ticks, taskfunc f, void* stuff);
//Init sets up timer 0, sets up interrupt handling for the timer, and starts
//the timer. Notice that the task manager monopolizes the timer, even
//though it only uses two match channels. The capture channels may be used,
//but interrupts on those channels may not.
    int begin();

//  ticks - how many ticks from now to fire this task
//  f     - task function to run
//  stuff - "stuff" pointer, a void pointer which points to whatever
//          the task wants. Typically a pointer to an object, so that
//          the task can call that object's methods.
//  0 if all is ok, some negative error code if not.
//    -1: Task time is too far
//    -2: Task time is too near (I don't think this can happen)
//    -3: Task list is full
    int schedule(uint32_t ticks, taskfunc f, void* stuff);
    int reschedule(uint32_t ticks, taskfunc f, void* stuff);

//The task interrupt handler works as follows. Tasks are keyed off of
//Timer 0, match channel 1 (match register 0 is set up to reset the timer
//every 1 second). When the timer 0 interrupt is received, we know that
//a task is due. The handler follows the head index to find the current
//task, and remembers it. It then erases the task from the task list by writing -1 to
//its ticks. It sets the head index to the next index in the saved
//copy, adds the tick counter of the next task to the T0MR1 match value
//register and subtracts 60M if necessary to handle wrapping around the
//top of the second. This means that the next task will generate an
//interrupt at EXACTLY the scheduled time. That interrupt will take a
//non-deterministic time to be handled depending on other interrupts and
//how much code is executed in the handler, but kickoff is exactly on
//schedule. Once the timer is set, it executes the task code and passes
//it the stuff pointer. The task is run at "interrupt priority" in other
//words as part of the interrupt handler, with the IRQ stack, in IRQ mode
//with other interrupts disabled. No other interrupts will be handled
//while the task is running, and all interrupts which occur will be
//delayed until after the task returns to the handler and the handler
//acks the interrupt and returns to normal mode.
    void handle(void);

extern TaskManager taskManager;

Premature optimization is the root of all evil, and using a linked list may have been premature. One cool feature I added because I needed it, is the reschedule() function. This one is meant to be called inside of a task, for accurately rescheduling the task in the future. The difference from normal schedule() though is trivial, in fact both call the same scheduleCore() function. The only difference is that reschedule() counts time from when this task was triggered, IE the current value of the T0MR1 register, while normal schedule() counts from now, IE the current value of the T0TC register. In any case, scheduleCore() manipulates the linked list, while handle() also manipulates the linked list. We have to be really careful about this and make sure that handle() is not in the middle of manipulating the list while it calls the task, which might call reschedule().

int TaskManager::schedule(uint32_t ticks, taskfunc f, void* p) {
  if(ticks>PCLK) return -1;
  return scheduleCore(TTC(timer)+ticks,f,p);

int TaskManager::reschedule(uint32_t ticks, taskfunc f, void* p) {
  if(ticks>PCLK) return -1;
  return scheduleCore(TMR1(timer)+ticks,f,p);

int TaskManager::scheduleCore(int mr, taskfunc f, void* p) {
  //special case if no tasks are currently scheduled:
  if(head<0) {
    return 0;

  //find an empty slot for the task
  int slot=0;
  while(tasklist[slot].ticks>=0 & slot<tasklist_size) slot++;
  if(slot==tasklist_size) return -3; //No available slots

  //First element of the list is different, since it doesn't matter
  //what it's .ticks is, we use the current MR1 to see how much longer
  //it has before it fires. Also handle the once-per-second overflow.
  uint32_t old_mr=TMR1(timer);
  if(old_mr<TTC(timer)) old_mr+=PCLK;
  if(mr<old_mr) {
    //This task fires before the first task in the list, so
    //Next after this task is the old head task
    //Set .ticks to zero so that handler (if we are called in a task)
    //adds zero to MR when it schedules this task
    //Does matter what next .ticks is now
    //The new slot is now the head of the list
    //Have to set MR since this is the next task to fire
    if(mr>PCLK) mr-=PCLK;
    return 0;
  //Walk the list. mr is now more like "delta mr". It is time from the last
  //task, and will be decremented further as the task list is walked
  int taskptr=head;
  while (tasklist[taskptr].next>0) { //while we haven't walked off the end of the list
    if(mr<tasklist[taskptr].ticks) {
      //We are at the right spot in the list
      //Point this task at the next one
      //Point the previous task at this one
      //Set the tick times
      //And we're done!
      return 0;
    //Subtract off the time this one will take...
    //and step to the next one
  //If we reach here, we have walked off the end of the list, so add to the end
  return 0;

void TaskManager::handle() {  if(head<0) {
    return; //If no tasks are scheduled, return immediately
  Task current(tasklist[head]);
  //erase the current task
  //set up the next task;
  //Call the task function. This might call reschedule() which might
  //change the task list
  //Schedule the next task
  if(head>=0) {
    while(TMR1(timer)>PCLK) TMR1(timer)-=PCLK;
  //ACK the timer
  //ACK the VIC

No comments:

Post a Comment