Developing a multitasking OS for ARM part 3

Okay.  We're almost done with the big bits of scary assembler.  Indeed, this post is almost totally assembler free, and will deal with some C functions and definitions we need for later.

We want to do something useful with what we have at the moment.  We could simply implement "something useful" as a C language routine called c_entry(), which would run in SVC mode with interrupts off. In some cases, that would be sufficient.  But it would hardly count as an OS, let alone a multitasking one.

So, let's look at what we want to do, make some definitions.  We want tasks that run in an unprivileged mode (i.e user mode) and are either preemptively swapped out by the OS in order to run another task, or which periodically yield control of the processor to another task.  They must be able to terminate.  For the moment, we won't worry too much about protected memory spaces, IPC, or any of that jazz (which complicate matters, but which will come later).

A task, must have its own, inviolate, set of registers, and its own stack.  It must also have some other information - entry point, state, and potentially priority.  My implementation is based on scheme, so a task must also have an environment, but that's not absolutely necessary.

/* function pointer type returning void and taking a pointer to an environment */
typedef void(*task_entry_point_t)(void * environment);


/* potential task states */
typedef enum {
  TASK_RUNNABLE,
  TASK_SLEEPING,
} task_state_t;


/* And the task itself */
typedef struct {
  void * stack_top;     /* limit of the task stack */
  void * stack_pointer; /* current stack pointer   */
  uint32_t priority:5;  /* priority, 0-31          */
  uint32_t state:1;     /* state, task_state_t     */
  uint32_t id:26;       /* task id                 */
} task_t;

Obviously, we need to know what the current task is, and have a list of other tasks that might want to run.  This is not identical to my code, as tasks are actually scheme objects, but you get the idea.

/* linked list structure */
typedef struct task_list {
  task_t * _car;
  struct task_list * _cdr;
} task_list_t;


/* some LISPy primitives */
#define CAR(x) (x)->_car
#define CDR(x) (x)->_cdr

#define SET_CAR(x,y) CAR(x)=(y)

#define SET_CDR(x,y) CDR(x)=(y)

/* We'll need these later */

#define nil  (task_list_t*)0

#define skip (task_t*)0

/* And the bits we need for the actual lists */
task_t * __current_task;
task_list_t * __priority_lists[31];


Now, the approach we'll be taking to multitasking is this:
Each task is created with a prority, and positioned as such in one of the priority lists.  Every time we need to find a task, we go through the priority lists, starting at zero, and ending at 31.  We look at each element in turn of the list by removing it from the head of the list and then grafting it onto the end of the list.  This way we round-robin schedule within each priority.  Only "runnable" tasks get scheduled, obviously.  If the task is actually the placeholder "skip", we will skip onto the next lowest priority. This way, all tasks eventually get a bite of CPU, with high priority tasks getting vastly more than the low priority ones.


Obviously, the initial setup of the lists is critical, and should be done in c_entry:


task_t * __sleep_task;


for (int i = 0; i < 31; i++) {
  __priority_lists[i] = (task_list_t *)malloc(sizeof(task_list_t));
  SET_CAR(__priority_lists[i], skip);
  SET_CDR(__priority_lists[i], nil);
}

__priority_lists[31] = (task_list_t *)malloc(sizeof(task_list_t));
SET_CAR(__priority_lists[31], __sleep_task);
SET_CDR(__priority_lists[31], nil);



The astute amongst you will notice the use of the C library function malloc() in there, despite not having a c library.  Don't worry about it.  It'll come later. Do worry about me not checking for errors :)


Note that priority 31 has *no* 'skip' entry, and points to a real task.  This task should not, under any circumstances, be missed out.


Now that's all done, we can find the next runnable task.


/* lispish function */
task_list_t * nconc(task_list_t * car, task_list_t * cdr) {
  if (car == nil) {
    return cdr;
  } else {
    task_list_t * x = car;
    while (CAR(x) != nil) x = CAR(x);
    SET_CDR(x, cdr);
    return car;
  }
}


task_t * next_runnable_task() {
  for (int i = 0; i < 32; i++) {
    while(CAR(__priority_lists[i] != skip)) {
      /* rotate the list */
      task_list_t * car = CAR(__priority_lists[i]);
      task_list_t * cdr = CDR(__priority_lists[i]);
      SET_CDR(car, nil);
      __priority_lists[i] = nconc(cdr, car);
      /* check runnability */
      if (car->_car->state == TASK_RUNNABLE)
        return car->_car;
    }
  }
  /* we should never get here, but just in case, eh? */
  return __sleep_task;
}


Now, that's all fine and well, but what about setting up tasks and actually making them swap?  Ah.  That's a bit more complex, and we're gonna have to delve down into assembler again.  I'll get into that next time round.


Until then, though, here's a couple of little functions we needed before.


void * malloc(size_t size) {

  extern char * __heap_top;
  extern char * __memtop;
  char * prev_heap_top = __heap_top;
  
  if (__heap_top + size > __memtop) {
    return (void *)0;
  }
  
  __heap_top += size;
  return (void *) prev_heap_top;

}


void sys_sleep() {
  for(;;){
    // ARMv6 Wait For Interrupt (WFI)
    uint32_t * reg = 0;
    __asm__ __volatile__ ("MCR p15,0,%[t],c7,c0,4" :: [t] "r" (reg));
  }
}