Saturday, January 7, 2012

Developing a multitasking OS for ARM part 3 1/2

Okay, so last time we looked at what we need to schedule and store top level information about tasks in our fledgling OS.  And it was pretty easy to do, because we could do all of it in C.  Unfortunately, things are about to get complicated again, because we're about to dive down into assembler again.

Whoopee!  I can almost hear the sound of "back" buttons being clicked as I type this.

So.  Multitasking.  How's that gonna work, then?  Largely speaking, there's 2 types of multitasking - preemptive multitasking, where tasks run for a specified amount of time then get forcibly swapped out, and cooperative multitasking, where tasks run until they decide to give some time to someone else.  We're going to implement (because there's precious little overhead in doing so) a hybrid where tasks can be "nice" and give time to others, but where the absolute maximum time they get is capped by a preemptive scheduler.

So.  Let's look at the sequence of events for a user-triggered task swap.  We want the user to use a line of code that looks like this (remember, I'm developing something that runs scheme...)


However, the user's code is running in user mode (remember the ARM processor states), and it can't directly access the task scheduler.  This is where software interrupts / SVC calls come in - the user's code *can* use the svc instruction.  This, in fact, is the beginning of what is known as a syscall interface, the way that unprivileged user code calls (or causes to happen) kernel functions.

Executing the svc instruction causes the following to happen:

  • CPSR_usr is transferred to SPSR_svc
  • PC is stored in LR_svc
  • Processor switches to SVC mode (SP_usr and LR_usr are now hidden by SP_svc and LR_svc, CPSR is identical except for processor state change)
  • PC is loaded with the address of the SVC exception handler

At this point, what we need to do is store R0-R12, LR_usr and PC (before entry to svc handler) into the user stack, in a known order, then save the user stack pointer to the task's "housekeeping" information, load the equivalents back in for the next task, and jump out of the handler back to user code.  We'll get onto that in a minute.

Preemptive task swapping will be done by using a timer interrupt.  Thus, for a preemptive task swap, the situation is quasi-identical, with _svc above replaced by _irq.  The only difference is that the PC stored to LR_svc is actually 4 bytes on from where we want to restart, so we need to remember to take that into account.

So.  How do we go about saving our information to the user stack?  This is made quite easy by the fact the user mode register are identical to the system mode registers.  So we need to save the svc/irq mode stuff (LR, SPSR) into the system mode stack, then swap into system mode and save the rest.  The first bit is covered by one instruction, which might have been made for the task:

srs (Store Return State) - store LR and SPSR of the current mode onto the stack of a specified mode

and, of course, its "twin"

rfe (Return From Exception) - load PC and CPSR from address

So, the preamble for the svc handler is as follows:

FUNC _svc_handler
srsdb sp!, #SYS_MODE /* save LR_svc and SPSR_svc to svc mode stack */
cpsid i,#SYS_MODE     /* go sys mode, interrupts disabled */

push {r0-r12} /* Save registers */

and r0, sp, #4 /* align the stack and save adjustment with LR_user */
sub sp, sp, r0
push {r0, lr}

and for an irq:

FUNC _irq_handler
sub lr, lr, #4 /* Save adjusted LR_IRQ */
srsdb sp!, #SYS_MODE /* save LR_irq and SPSR_irq to system mode stack */
cpsid i,#SYS_MODE /* Go to system mode */
push {r0-r12} /* Save registers */
and r0, sp, #4 /* align the stack and save adjustment with LR_user */
sub sp, sp, r0
push {r0, lr}

Note that the only difference is that the irq handler adjusts the return address (as we want to go back to the interrupted instruction, not the next one).

Given that we are now *always* in system mode, exiting from either handler is identical:

pop {r0, lr} /* restore LR_user and readjust stack */
add sp, sp, r0
pop {r0-r12} /* and other registers */
rfeia sp! /* before returning */

I'll move onto how to implement the guts of the two handlers in the next post.  But before we go, here's how we set up a task in "C" land.

Remember, when we switch into a task, we will be pulling a stored process state from the task's stack into the registers, and then restoring the PC and CPSR, also from the task's stack.  Setting up a task, then, involves "faking" the preamble of the exception handlers above.  Note the use of exit_fn as the value of LR_usr, this is where we go when a task dies, and is used to clean up after task exit, and the use of 'entry' (the address of the task's entry function) as the value of LR_svc/irq, which will be used as the "return" address from the exception handler.

The use of exit_fn means we can schedule "one-shot" tasks (which not all realtime OSs can do).  Hooray for us.

  // Allocate stack space and the actual object
  task_t * task = malloc( sizeof(task_t) );
  void * stack = malloc( stack_size * 4 );
  unsigned int * sp = stack + stack_size;
  task->stack_top = stack;
  task->priority = priority;
  task->state = TASK_SLEEP;
  task->id = (unsigned int)task & 0x3fffffff;
  *(--sp) = 0x00000010;             // CPSR (user mode with interrupts enabled)
  *(--sp) = (unsigned int)entry;  // 'return' address (i.e. where we come in)
  *(--sp) = 0x0c0c0c0c;             // r12
  *(--sp) = 0x0b0b0b0b;             // r11
  *(--sp) = 0x0a0a0a0a;             // r10
  *(--sp) = 0x09090909;             // r9
  *(--sp) = 0x08080808;             // r8
  *(--sp) = 0x07070707;             // r7
  *(--sp) = 0x06060606;             // r6
  *(--sp) = 0x05050505;             // r5
  *(--sp) = 0x04040404;             // r4
  *(--sp) = 0x03030303;             // r3
  *(--sp) = 0x02020202;             // r2
  *(--sp) = 0x01010101;             // r1
  *(--sp) = (unsigned int) env;     // r0, i.e. arg to entry function

  if ((unsigned int)sp & 0x07) {
    *(--sp) = 0xdeadc0de;           // Stack filler
    *(--sp) = (unsigned int)exit_fn;              // lr, where we go on exit
    *(--sp) = 0x00000004;           // Stack Adjust
  } else {
    *(--sp) = (unsigned int)exit_fn;              // lr, where we go on exit
    *(--sp) = 0x00000000;           // Stack Adjust
  task->stack_pointer = sp;

No comments:

Post a Comment