Last time we got the kernel switching back and forth between multiple tasks. This time we’re going to get a simple timer to wake up the kernel at fixed intervals.

Motivation

So far we’ve been interacting with hardware when we want to. Writing to the serial port when we have something to print, for example. Why would we want to let the hardware interrupt what we’re doing?

A few reasons:

1. Currently, our user mode tasks have to call a syscall on purpose in order for any other task to be able to run. This means one task can run forever and block anyone else from running (called starvation). So we at minimum need some way to interrupt running tasks (called preemption).
2. The hardware knows when it’s ready. It is way more efficient to let the hardware say “I’m ready now” then to keep asking it.
3. The hardware may actually stop being ready by the time we get around to talking to it again. We want to talk to the hardware during the window when it’s able to talk

Enabling a Simple Timer

Before we get to the serial port, there is an even simpler piece of hardware we can work with first: timers. Timers just take a value and count down to zero, sort of like an alarm clock.

I could make you go look up in the user guides what all the magic numbers for our timers are, but I’m a nice guy, so here’s the ones we need to add to versatilepb.h:

/* http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0271d/index.html */
#define TIMER0 ((volatile unsigned int*)0x101E2000)
#define TIMER_VALUE 0x1 /* 0x04 bytes */
#define TIMER_CONTROL 0x2 /* 0x08 bytes */
#define TIMER_INTCLR 0x3 /* 0x0C bytes */
#define TIMER_MIS 0x5 /* 0x14 bytes */
/* http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0271d/Babgabfg.html */
#define TIMER_EN 0x80
#define TIMER_PERIODIC 0x40
#define TIMER_INTEN 0x20
#define TIMER_32BIT 0x02
#define TIMER_ONESHOT 0x01

Now add the following somewhere near the top of your main:

*TIMER0 = 1000000;
*(TIMER0 + TIMER_CONTROL) = TIMER_EN | TIMER_ONESHOT | TIMER_32BIT;

The timer on our QEMU system defaults to using a 1Mhz reference, which means that it ticks 1000000 times per second. So, by setting it’s value to 1000000, it will reach 0 after one second.

Then, on the second line, we enable the timer, set it to “oneshot” mode (that is, it will just stop when it’s done counting, we’ll see another mode later), and set it to 32BIT mode (so that it can hold really big numbers).

Now, somewhere in your while loop, put this:

if(!*(TIMER0+TIMER_VALUE)) {
   bwputs("tick\n");
   *TIMER0 = 1000000;
   *(TIMER0 + TIMER_CONTROL) = TIMER_EN | TIMER_ONESHOT | TIMER_32BIT;
}

We’re just printing out “tick” if the timer has reached 0, and then resetting and re-enabling the timer.

Build and run your kernel. It should still work as before, but now it will also print out “tick” once per second.

Back to the Vector Interrupt Table

The CPU uses the same mechanism for hardware interrupting operation (often referred to as an “interrupt request” or IRQ) as it used know where to jump when we used svc. We need to add an entry to the right place. Here’s the new code for bootstrap.s:

interrupt_table:
ldr pc, svc_entry_address
nop
nop
nop
ldr pc, irq_entry_address
svc_entry_address: .word svc_entry
irq_entry_address: .word irq_entry
interrupt_table_end:

IRQ entry point

Back over in context_switch.s, irq_entry is going to be very similar to svc_entry, but with some changes to handle an IRQ instead of a syscall.

As soon as we enter system mode, we need to push the value of r7 onto the task’s stack (because that’s what the syscall wrapper does, and we need to set things up to look the same). The syscall puts the number identifying the syscall into r7, so we should come up with something that will identify an IRQ and put that there instead. To make sure the number never clashes with a syscall number, lets use negative numbers:

push {r7} /* Just like in syscall wrapper */
/* Load PIC status */
ldr r7, PIC
ldr r7, [r7]
PIC: .word 0x10140000
/* Most significant bit index */
clz r7, r7
sub r7, r7, #31

That value at PIC is the address of the interrupt controller status (that is, the value that can tell us which interrupts are currently firing) and then we just do some operations on that value to find out what the most significant bit set in the value is, and transform that into a negative index to use for the identifier of this IRQ.

The only other weird thing is that we have to get the value of the lr from IRQ mode instead of Supervisor mode, and the value is set to the instruction after the one we should be returning to, so we’ll need to subtract 4:

msr CPSR_c, #0xD2 /* IRQ mode */
mrs ip, SPSR
sub lr, lr, #0x4 /* lr is address of next instruction */
stmfd r0!, {ip,lr}

So those bits, together with what we already had from svc_entry give us this complete entry point code:

.global irq_entry
irq_entry:
	/* Save user state */
	msr CPSR_c, #0xDF /* System mode */

	push {r7} /* Just like in syscall wrapper */
	/* Load PIC status */
	ldr r7, PIC
	ldr r7, [r7]
	PIC: .word 0x10140000
	/* Most significant bit index */
	clz r7, r7
	sub r7, r7, #31

	push {r0,r1,r2,r3,r4,r5,r6,r7,r8,r9,r10,fp,ip,lr}
	mov r0, sp

	msr CPSR_c, #0xD2 /* IRQ mode */
	mrs ip, SPSR
	sub lr, lr, #0x4 /* lr is address of next instruction */
	stmfd r0!, {ip,lr}

	msr CPSR_c, #0xD3 /* Supervisor mode */

	/* Load kernel state */
	pop {r4,r5,r6,r7,r8,r9,r10,fp,ip,lr}
	mov sp, ip
	bx lr

A Small Problem

We’re pushing the value of r7, but where is it going to get popped? The syscall wrappers do both the push and the pop, but in the case of an IRQ we’re pushing in the entry point, and we have no easy way to tell activate that it’s exiting from an IRQ instead of a syscall. Hmm.

The solution to this that I’ve chosen is to remove the pop instruction from the syscall wrappers, and add an identical instruction to right after the pop instruction already in activate. Now the pop always happens.

More Magic Numbers

We hardcoded a single magic number into our assembly, but luckily that’s the only one our assembly code will need. In fact, we should not need any more assembly! (Unless we wanted to implement other sorts of hardware exceptions, which we may get to.) We do need that and a few other interrupt-controller related magic numbers in our C code too, so here’s the stuff for versatilepb.h:

/* http://infocenter.arm.com/help/topic/com.arm.doc.dui0224i/I1042232.html */
#define PIC ((volatile unsigned int*)0x10140000)
#define PIC_TIMER01 0x10
/* http://infocenter.arm.com/help/topic/com.arm.doc.ddi0181e/I1006461.html */
#define VIC_INTENABLE 0x4 /* 0x10 bytes */

Enable the Interrupt

We have to tell the timer to generate interrupts, and we have to tell the interrupt controller to pass those interrupts through. So, replace your current one-shot timer code with this:

*(PIC + VIC_INTENABLE) = PIC_TIMER01;

*TIMER0 = 1000000;
*(TIMER0 + TIMER_CONTROL) = TIMER_EN | TIMER_PERIODIC | TIMER_32BIT | TIMER_INTEN;

Note that we’re also using a new timer mode here. Periodic mode will automatically cause the timer to restart from the value we set when it hits 0, which is perfect for when we’re getting an interrupt instead of waiting until the value hits 0.

Handle the Interrupt

Now we have to add a case to our switch statement for this request:

case -4: /* Timer 0 or 1 went off */
	if(*(TIMER0 + TIMER_MIS)) { /* Timer0 went off */
		*(TIMER0 + TIMER_INTCLR) = 1; /* Clear interrupt */
		bwputs("tick\n");
	}

The way our hardware is set up, the interrupt is actually the same for either timer 0 or timer 1. Now, we know that we’ve only set timer 0, but that’s lazy. TIMER_MIS is the offset where we’ll find a flag telling us if Timer0 was the one that is causing the interrupt. After checking that, we set a value on the timer to clear the interrupt (basically to say that we’ve seen it so that it won’t call us again unitl the next interrupt). Finally, print out “tick”.

As it is, this code should operate exactly the same as the version without the interrupts.

Pre-emption

Up until now, we’ve needed the dummy syscall syscall in an infinite loop at the end of every task in order to let other tasks run. Since the timer interrupts the tasks now, we don’t need them to interrupt themselves. Remove all references to the syscall syscall and try running the kernel again. Now you’ll note that the first task just stays in its infinite loop and does not let the other task keep running. Does not, that is, until the timer goes off and you see “tick” printed for the first time, after which the tasks switch. So the tasks are now being properly interrupted even if they do not give up control!

We’re done!

The kernel now has all the machinery it needs to be able to handle hardware interrupts, and tasks are being pre-empted by the timer. Next time we’ll start looking at IPC.

The code so far is on GitHub.

Updated 2012-33 to fix a bug in the context switch assumptions.
Edited for clarity, 2012-34.

Last time, we got our kernel to set up space for a task, and run that task in user mode. This time we’re going to add a facility for the user mode task to call back into the kernel.

Syscalls

But wait! Didn’t I say last time that one of the things user mode tasks cannot do is change the CPU mode? Well, yes, they can’t change it directly. What they can do is trigger an event that will make the CPU switch to supervisor mode and then jump to some predefined bit of code. That way, there’s no security problem, only kernel code is running in supervisor mode, but the user mode task can still ask the kernel to do things for it.

The instruction that lets us do this on an ARMv6 CPU is svc (used to be called swi). It takes an immediate value as an “argument”, which it actually does nothing with. If the kernel wants to use that number for something (like specifying what the user mode task wants done), it has to read the number right out of the instruction in RAM. This is doable, but not always ideal, and so some kernels (such as modern Linux) actually just always use a zero, and then store information they want to pass elsewhere.

Vector Interrupt Table

The svc instruction actually causes an interrupt. Interrupts are signals that (when they’re enabled) cause the CPU to switch modes and jump to some predefined instruction. What instruction will it jump to? Well, ARM CPUs have something called the vector interrupt table that is at the very start of RAM. These locations are where it will jump to (each word, starting at 0x0, is the location of a particular sort of interrupt, up until there are no more interrupt types).

That may not seem very useful. We can only execute one instruction? Well, yes, but that instruction can jump us to somewhere more useful. Now, your first thought may be to put a branch instruction there. Great idea, but it won’t work. Branch instructions are calculated relative to their position in the linked binary. If we copy one of them to another location in RAM, the offset will be wrong. We need to use a load instruction to load an absolute value into the program counter. What value should we load? The address of a function in our kernel, of course! It turns out that the assembler contains a syntax for including the address of a function directly, which is then an absolute value and so does not move when we copy it.

Here’s what the new bootstrap.s looks like:

.global _start
_start:
	mov r0, #0x08
	ldr r1, =interrupt_table
	ldr r3, =interrupt_table_end
keep_loading:
	ldr r2, [r1, #0x0]
	str r2, [r0, #0x0]
	add r0, r0, #0x4
	add r1, r1, #0x4
	cmp r1, r3
	bne keep_loading

	ldr sp, =0x07FFFFFF
	bl main

interrupt_table:
	ldr pc, svc_entry_address
	svc_entry_address: .word svc_entry
interrupt_table_end:

Why do we need to copy two instructions? Well, even that load instruction is loading from a relative address. Luckily if we move them both then the relative position remains the same. This may look a bit complicated, and that’s because it is. You could just copy the two words directly across, but this way we have a loop that copies everything from our interrupt table section, so we can easily add other interrupt handlers to it later. You’ll note we started at 0x8 instead of 0x0, because that’s where the SVC handler is, so if we want to add ones that come before 0x8, we just have to remember to change the base address at the start. With some hacks we could do the copying part in C, but for this example I decided that keeping all the bits for this in assembly was easiest.

Syscall Wrapper

We need a way for our C code to call the svc instruction. Since we don’t have anything we really need to pass through, we’ll just add a dummy wrapper for now.

Create a new file called syscalls.s and add it to the Makefile as a dependency of kernel.elf. Put this in it:

.global syscall
syscall:
	svc 0
	bx lr

Pretty simple. It just activates the svc, and then when it comes back jumps to the caller (note that this assumes the registers it had before it called svc are reset before it comes back).

You’ll also need to add a line to asm.h:

void syscall(void);

Save Kernel State

Now, let’s think about what we want the kernel to do when it actually gets control back. We’d like to go back to the point in our kernel code we left off when calling activate in the first place. The problem is, we’ve not got any clue where that was! In loading the user mode task state, we did not keep around any information about what state the kernel was in. Let’s add that to activate now:

mov ip, sp
push {r4,r5,r6,r7,r8,r9,r10,fp,ip,lr}

Put that at the top of activate, before we begin messing about with the registers. That’s all the kernel state we need to save!

SVC Entry

Alright, we’re now ready to define our first version of the svc_entry function. All we really want to go at this point is get the kernel back into a state where it can run, and then return to our code. We’ll put this in context_switch.s:

.global svc_entry
svc_entry:
	pop {r4,r5,r6,r7,r8,r9,r10,fp,ip,lr}
	mov sp, ip
	bx lr

Just reverse the save we just did, and jump back to where we came from in the kernel. How is lr where we came from? Well, you’ll have noted that when we call functions (and the C compiler does this as well), we use bl, which saves the address of the instruction after itself in lr before jumping to the function.

Alright, add a call to syscall to the end of first and then add another bwputs call after the activate call in main, build, and run. You should see your new message printed last.

Code so far on GitHub

Heading Back to User Mode

Add another print and another syscall to first, and another print and call to activate to main. Compile and run your code. What do you see?

When we call activate again, the user mode task re-starts at the beginning! That’s not what we want, but it makes sense. We never saved our place inside the user mode task. In fact, we don’t even have a reference to where its stack was when it called the syscall, so we’re just going back with the stack from before. That’s not going to work. We need to add some code to our SVC entry to save the user mode task’s state. If you recall the way we set up the task before, you’ll now see why. The way the stack looks after we save our state on it is exactly the same as the way we set it up! Everything will be where activate expects it:

msr CPSR_c, #0xDF /* System mode */
push {r0,r1,r2,r3,r4,r5,r6,r7,r8,r9,r10,fp,ip,lr}
mov r0, sp
msr CPSR_c, #0xD3 /* Supervisor mode */

mrs ip, SPSR
stmfd r0!, {ip,lr}

There, all the registers are on the user stack. We use stmfd which is just like push, but lets us operate on another register. You’ll note we had to save both versions of lr. One is state for the syscall wrapper to use, the other is the address inside the syscall wrapper we need to jump back to later. Now we just need some way to get the new location of the top of the stack back to the kernel.

Conveniently, our C code expects the return value of a function to be in r0, which is where I’ve put the user mode sp in this example. Just change the definition of activate in asm.h to return the right type, and then assign the return value somewhere and pass that to the next call to activate. You can now keep calling into your user mode task as many times as you want!

That’s It!

We now have a kernel that can start a user mode task, and switch back and forth between the kernel and the user mode task at will. Next time we’ll look at multitasking and maybe some other stuff.

Code for this post is on GitHub.

Updated 2012-33 to fix a bug in the context switch assumptions.
Edited for clarity, 2012-34.

Last time, we got a basic bit of C code bootstrapped and running all by itself on QEMU. This is often called “bare-metal” programming. This time we’re going to add to that and do something a bit more complicated: we’re going to run a single user-mode program on our kernel.

What is User Mode?

User mode is the name given to the mode we put the computer in when running anything other than the kernel. This often has implications for memory protection and similar, but we don’t have any of that. For us it’s just going to be the CPU mode in which certain things (such as changing CPU modes) cannot be done.

User mode also often refers to the slices of the system resources given to different processes, etc, such that they can all be run on the same computer without interfering with each other.

First, some abstractions

We hard-coded some values and functionality last time to write to the serial port. That code was very simple for printing one statement, but we may want to clean it up a bit if we’re going to use the serial port a lot.

First, let’s pull out everything machine-specific from kernel.c and put it in a header file for the machine, call it versatilepb.h:

#define UART0 ((volatile unsigned int*)0x101f1000)

So far we just throw the characters at the serial port as fast as we can, and hope they get caught. That will probably always work on QEMU, but will not work on real hardware, so let’s add the ability to check if the serial port can handle a byte right now. For that we’ll need two more constants:

#define UARTFR 0x06
#define UARTFR_TXFF 0x20

UARTFR is the offset (in words) from the UART0 base address of the flags for the serial port. UARTFR_TXFF is the mask that gets the bit representing if the transmit buffer is full.

Now you can put the following at the top of kernel.c:

#include "versatilepb.h"

void bwputs(char *s) {
	while(*s) {
		while(*(UART0 + UARTFR) & UARTFR_TXFF);
		*UART0 = *s;
		s++;
	}
}

Now you can replace the big mess in main with bwputs("Hello, World!\n"); or any other message. Much cleaner!

Code so far on GitHub

Calling Into Assembly Code

Last time, we had a small piece of assembly code that called in to our C program. This time, we are going to want to call into assembly code from our C code. If you are on Ubuntu or some other systems, your C compiler may be defaulting to generating “thumb mode” instructions, which are not what we need to use for our assembly code. So we need to tell the C compiler to generate normal ARM instructions. To do this with gcc, add -marm to the end of your CFLAGS

A User Program

Create a simple “user program” in the form of a function in kernel.c called first that just prints and then hangs (since we will not build the ability to get out of user mode until later):

void first(void) {
	bwputs("In user mode\n");
	while(1);
}

Assembly stub

Create a new file called context_switch.s with the following:

.global activate
activate:

And a new file called asm.h with the following:

void activate(void);

Include this new header file into kernel.c so that you can call the assembly stub from your C code, then add a call to activate to your main.

Finally, add context_switch.o as a dependency to kernel.elf in your Makefile so that it will get built.

The Context Switch

Alright, what are the absolute minimum things we need our switch to user mode (called the “context switch”) to do? Well, it the very least we need a way to start running some function in user mode.

The way to switch an ARM system into user mode is to use the movs instruction to put some address to jump to (like the address of our function) into the pc register (the “program counter”, which is where the CPU is currently executing). But what mode will the CPU enter when we do this? The answer is that it will read the contents of a special register called SPSR (Saved Processor Status Register) and use that to change CPSR (Current Processor Status Register), and thus change modes. Couldn’t we just change CPSR directly? Because we’re not in user mode, we could, but since we want to jump into our function the moment we switch modes, this is the safest way to do it:

mov r0, #0x10
msr SPSR, r0
ldr lr, =first
movs pc, lr

0x10 is just the value that sets the bit meaning “user mode”. We set that to SPSR, load the location of first and then movs there.

You can stick that at the start of activate and try to run that if you like, but it won’t work. Why is that? Remember how we had to set up the stack in order to jump into C code? Well, it turns out that one of the differences of user mode is that it uses a different sp register. This can be very handy later when we’re doing more complicated things, but for now we can just set the user mode stack to be the same as the kernel stack, by adding the following before the movs:

mov ip, sp
msr CPSR_c, #0xDF /* System mode */
mov sp, ip
msr CPSR_c, #0xD3 /* Supervisor mode */

So what are we doing here? We copy our current sp to ip (because we’ll have a different sp in user mode, so we need to copy it somewhere), then we set a part of CPSR directly to enter “system mode”. What is system mode? It’s a special mode on the ARM processor that lets us access the registers as though we were in user mode, but still be able to do privileged things. We set user mode sp to our copy, then switch back to supervisor mode (which is where we normally operate in the kernel).

If you build the kernel now, and run it under QEMU, you should get “In user mode” printed out. Good job!

Code so far on GitHub

A Better Stack

Using the same kernel stack for our user mode program isn’t going to work very well if we want to be able to pause the program and go back to it, because other things will use the kernel stack in between, so we really want the program to have it’s own stack.

First, declare some space for your user stack:

unsigned int first_stack[256];

Then pass first_stack + 256 to activate, and change asm.h to have activate take an argument.

The first four arguments to an assembly call come in as r0-r3, so we can easily access this parameter inside activate:

msr CPSR_c, #0xDF /* System mode */
mov sp, r0
msr CPSR_c, #0xD3 /* Supervisor mode */

One less line, since we can access r0 from user mode directly.

Less hardcoding

The program should still run, but now it’s using its own stack. We still have the value of SPSR and the name of the function we’re calling hardcoded into the assembly. We could pass these as parameters, but then we would have to remember them in a special way when it comes to being able to enter and re-enter the same user mode function multiple times (since the current stack, CPU mode, and entry point can change between calls), so it’s actually easiest to store these two additional values on the user mode program’s stack. We will store them in special positions so that all the user mode registers can be saved along with them easily.

We’ll want to move the calculation of the end of the stack up, so that we can put our data into in:

unsigned int *first_stack_start = first_stack + 256 - 16;
first_stack_start[0] = 0x10;
first_stack_start[1] = (unsigned int)&first;

You’ll note the cast to (unsigned int) of the function pointer. This is mostly to make the compiler not warn us about using a function pointer as data. You should now pass first_stack_start to activate. If you want to, you can test that it still works, but we aren’t actually using this new data yet.

We’ve done a lot of work on the assembly, and are about to change it quite a bit, so I’ll reproduce the whole context switch here with the changes to use these values:

.global activate
activate:
	ldmfd r0!, {ip,lr} /* Get SPSR and lr */
	msr SPSR, ip

	msr CPSR_c, #0xDF /* System mode */
	mov sp, r0
	pop {r0,r1,r2,r3,r4,r5,r6,r7,r8,r9,r10,fp,ip,lr}
	msr CPSR_c, #0xD3 /* Supervisor mode */

	movs pc, lr

This loads the first two elements from the passed-in stack to SPSR and lr (ldmfd, when coupled with the ! on the first argument, is the same as pop, but works with any register instead of just sp), then we switch to usermode and set the stack to r0, as before. Finally we use the pop instruction to load the rest of the stuff into our registers. We have nothing in there just now, but we’ll use more later, and this also makes the stack skip over all that stuff so that the process can use all of the space.

You’ll note we had to set lr twice. This is because, like sp, lr has a different version used in user mode from the one used in supervisor mode.

That’s it!

We now have a kernel that sets up a user mode task and then switches to it. Next time: getting back out of user mode!

The code for this post is on GitHub.