Archive for February, 2012

Archive for February, 2012

Writing a Simple OS Kernel — Part 5, Hardware Interrupts

Posted on

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.


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:

/* */
# TIMER0 ((volatile unsigned int*)0x101E2000)
# TIMER_VALUE 0x1 /* 0x04 bytes */
# TIMER_CONTROL 0x2 /* 0x08 bytes */
# TIMER_INTCLR 0x3 /* 0x0C bytes */
# TIMER_MIS 0x5 /* 0x14 bytes */
/* */
# TIMER_EN 0x80
# TIMER_32BIT 0x02

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

*TIMER0 = 1000000;

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:

   *TIMER0 = 1000000;

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:

ldr pc, svc_entry_address
ldr pc, irq_entry_address
svc_entry_address: .word svc_entry
irq_entry_address: .word irq_entry

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, # /* IRQ mode */
mrs ip, SPSR
sub lr, lr, # /* 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
	/* Save user state */
	msr CPSR_c, # /* 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, # /* IRQ mode */
	mrs ip, SPSR
	sub lr, lr, # /* lr is address of next instruction */
	stmfd r0!, {ip,lr}

	msr CPSR_c, # /* 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:

/* */
# PIC ((volatile unsigned int*)0x10140000)
# PIC_TIMER01 0x10
/* */
# 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:


*TIMER0 = 1000000;

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 */

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.


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.

Dystoparx — Part 15

Posted on

Jack is outside her apartment. He slipped into the building behind someone else so that he wouldn’t have to push the buzzer. Now he’s just standing here.

He left the datacentre mostly under control. One of the ops came in and got a run-down of what’s going on. Just keep the place running, that’s all the op has to do. The attack should be basically harmless at this point.

Well, harmless to the datacentre.

Jack’s name is now directly associated with the attack as “the guy who first reported it.” Not good if his suspicions are correct. Maybe Nicnus is right, maybe he should—

Her door opens. It’s her. Of course, who else would it be?

She seems a bit surprised, “You came?”

“Uh…” He’s not sure he was being expected, but, “Yes?”

She smiles a sort of sad smile, then, “Come in.”

He comes in. Not sure where this is going. Maybe her friend told her something? Maybe he’s caught in some sort of unclear set-up? Best to just wait it out for now. So far she’s not unhappy with him.

Now he’s sitting in her living room. She’s in the kitchen. Probably preparing beverages. As ridiculous as it sounds, in this particular case he likes it. It’s a welcome form of procrastination.

He feels his phone vibrate. No. His attention is on her now. It vibrates again. No.

She is back with the beverages. On the coffee table. Now she is across from him, sipping. Looking expectant. Crap. He probably should have had a plan. Or… he thinks back over his conversation with her friend and decides to try something.

“So… I have absolutely no plan here.”

She says nothing, but at least she does not exhibit any signs of being upset by this. He decides to sip his drink and wait. The mug contains some sort of tea he could never get the name right for. It’s her favourite, and really not his sort of thing. He sips anyway.

His phone vibrates again. He is still ignoring it. Sipping. Willing his mind not to drift elsewhere. Here is where he needs to be right now. All of him.

“I’ve missed you.” She says it like it should be obvious.

“I thought you didn’t want to see me.”

She shakes her head in disgust, “That’s always been your problem.”

He raises an eyebrow at her and says nothing. Either an explanation is coming, or else he’s going to have to make it more obvious that he needs one.

“Why did you think I didn’t want to see you?”

He sips for a few moments, as if he is thinking. She needs to see him thinking. Finally, “You said as much.”

“Did I?”

He nods.

“Probably. Sounds like something I might have said. Your problem is that you take everything at face value.” She tosses her hair and continues to sip her tea.

He’s quite impressed. They’re having what is effectively a mostly-rational discussion about what happened. He never would have expected this. As he takes his next sip he realises something: this is his problem. He doesn’t give her enough credit. That she should be discussing the situation with him in a rational manner should not be impressive.


Nor should it be expected. Huh.

“Because you didn’t want to see me then.” He says this slowly, as it comes to him, “But you didn’t want to have to tell me when that changed. Didn’t want to, because it seemed obvious that it would change somewhat quickly. You thought I should know that you would eventually want to see me.”

She is saying nothing, but her eyes say all he needs to know. His phone vibrates again.

“I know I can be hard to handle,” he pays his phone no mind, “I mean, I don’t take the world lying down. I expect clarity in communication. I want to correct errors wherever I see them—” He cuts himself off, a list of his faults is not going to help here. She knows what her problem is. “I can relax all that,” He’s sure that he can, “I mean, I can be more understanding. I can try to read into what you’re saying just a little more. Let trivialities be trivial a little bit more often…”

He doesn’t want to say what he has to say next. Things are going so well. He is realising, though, that as much as he wants this to work, it is not his whole world. So he says it. “I’m not going to change who I am, though. I’m not going to stop analysing the world. I’m not going to instantly know your every wish. You still have to tell me things. More than once. More clearly. Maybe even more than you would normally have to with other guys. Because I’m not them.”

His phone is vibrating constantly now, as though a phone call is coming in.

She finally sets her tea down and speaks, “You’re right. This isn’t all your fault, and I can try harder. Your willingness to take the first step is all I really needed.” She pauses for a moment, then shakes her head, “Now answer your phone before you go insane.”

Bill is not sure how he feels. The operation was completely successful, and yet it had been a colossal failure. Every single person they had set out to question had been easily found and questioned. None had evaded them, none of their information had led them to a dead-end. By operational standards, a resounding success.

Not a single person they had questioned, however, had ties to child pornography groups. At least, not so far as they could discern. Not a one. Well, except for the teenagers they had caught with pictures of girlfriends and boyfriends. Hardly the sort of contraband they were after.

What had gone wrong? The FBI had nailed a guy based on their surveillance, how could a large-scale operation here fail to be at least a little successful?

The techies told him it was the nature of the surveillance. People with MusicBox knew it was tapped. They were unlikely to store their pornography on the same machine. Bill knew something, however, that the techies did not know. Data was also being piped in from email and web histories in other ways. Ways which Bill did not himself understand. Then again, some of the techies knew some of these things.

Bill is now looking over the data he has on the successful FBI operation. The one that convinced him that this could work. The pervert had sent an email to his mother, that’s how they had found him. They had picked up the email on his mother’s machine.

Suddenly, Bill has an insight. They had been looking for suspicious material, and tracking that material to the machines it had passed through. Those machine were accessed who knows how, or maybe the wifi connections associated with the machines were compromised, whatever. The success with the FBI had been tracking activity from someone suspicious to a known connection, then back-tracing the activity to the real source somehow. The technical details don’t matter. Bill doesn’t really understand them. The strategy matters. Stop spying only on suspicious data, and start trying to correlate it with otherwise innocent data!

This is great. This can work. He cannot task anyone to do it, however, until the politics gets sorted out. To ask anyone to do this would be to admit that they were not only interested in raw MusicBox data. With the right spin, the operation could still provide the media bomb they need.

He dials his supervisor.

Acklas hangs up as soon as Jack answers. Soon Jack has caught up on the messages they’ve been sending him and begins to reply.

14:00 <acklas> So, I just quit my job.

14:02 <nicnus> Awesome?

14:02 <acklas> nicnus: I’ll let you know. I don’t suppose there are openings at your startup?

14:03 <nicnus> We’re “always hiring”, so maybe.

14:05 <nicnus> Woah! Have you seen this thing about the kiddie porn arrests?

14:06 <acklas> Just a sec…

14:10 <acklas> Woah. That is not how it seemed to be going down at all…

14:12 <nicnus> You mean the part about how this shows there is “more of this problem than we, as a society, want to admit”?

14:12 <acklas> Yeah. From what I understood, it was mostly a junk operation. Scaring old ladies and single mothers, instead of doing their jobs.

14:13 <nicnus> Apparently, they’d rather not remember it that way.

14:15 <acklas> Apparently, they’d rather ask for sweeping surveillance provisions. Because, you know, this proves they can totally handle it.

14:15 <nicnus> No, this proves they might be able to scare people into thinking we need it.

14:15 <acklas> Suresure. Man, I found one article that says the USA “has been doing something similar for some time”

14:16 <nicnus> First I’ve heard of it. I think it’s more that they’re also *trying* to get something in place.

14:16 <acklas> Yeah. The security community would have seen something by now if they were doing it before the laws were in place.

14:20 <nicnus> Jack!

14:20 <acklas> What?

14:20 <nicnus> jjdavis: What, exactly, did you stumble on again? The US gov’t snooping emails?

14:21 <acklas> Woah, when did this happen?

14:21 <nicnus> During your meeting.

14:22 <acklas> jjdavis: is this true?

14:23 <nicnus> jjdavis? This is a big deal, man. You can’t stay down there.

14:24 <acklas> Yeah, if they’re spying semi-illigally…

14:24 <nicnus> If it’s not even legal… yeaah

14:35 <nicnus> jjdavis?

14:40 <nicnus> Oh my goodness, they’ve got him.

14:45 <acklas> dan’t be silly. he’s at his girl’s, remember?

14:50 <acklas> Ok, I’ll call him. You know. He should at least know about this.

** jjdavis reads

14:57 <jjdavis> nicnus: like I said, I’m not going anywhere. I’ll be ok

14:58 <acklas> Sure, I mean, nicnus is a bit paranoid. Still, though…

14:59 <jjdavis> From the way that article reads, it’s about to get hot up there as well.

15:00 <nicnus> maybe, but you didn’t *find* them up here.

15:01 <jjdavis> We’ll see

15:03 <acklas> How did it go with your SO, anyway?

15:05 <jjdavis> I’m still here. We’ve sort of patched things up in principle.

15:06 <acklas> I guess that’s good, then.

15:07 <nicnus> jjdavis: I’m overnighting you one of our devices, set with a key I’ll give to acklas as well.

15:09 <jjdavis> nicnus: sure

15:16 <acklas> nicnus: how hard would it be to modify your MusicBox blocker to instead spam the crap out of the RCMP?

15:18 <nicnus> Pretty easy. I think someone already did it in principle. why?

15:20 <acklas> I’ll get back to you on that.

Acklas is thinking. If the States is already on it, then Canada might not be so far behind. There needs to be resistance to the surveillance before it becomes law. After that, everything just gets harder. Even Nicnus’ magic crypto doesn’t stop spyware. Doesn’t stop email snooping. At least, not by itself.

If they were going to use their failure to tell the media why they needed more power (“they” in this case being some nameless force Acklas paints as being behind the whole mess), then Acklas could maybe use something else to sway the media another way. A battle in the media might be a battle that could be won.

Why has he not thought of this before? Man. Half a day out of the cubicle and already his creative problem-solving juices are flowing again. He has nothing else that he needs to be doing, and money is not going to be an issue for awhile.

If this is what’s necessary to keep from living in fear, then Acklas will bring the fight.

Writing a Simple OS Kernel — Part 4, Multitasking

Posted on

Added a description of fork, 2012-36.

Last time we got our kernel switch back and forth between a user mode task. The focus in this post is going to be adding the ability to run multiple tasks.

Hack Two Tasks in There

Our kernel currently has no way for tasks to exit, so we need to make sure they never try to return, since that will probably cause an error and hang the system (in the best case). So change the syscall invocation at the end of first to be in an infinite loop, such that if the task gets re-activated after it is done it just immediately calls back into the kernel.

Then, add a second function so that we have something else to run:

void task(void) {
	bwputs("In other task\n");
	while(1) syscall();

We’re going to run two tasks, so change the first_stack and first_stack_start to something like:

unsigned int stacks[2][256];
unsigned int *tasks[2];

And setup both tasks, in basically the same way as we did before:

tasks[0] = stacks[0] + 256 - 16;
tasks[0][0] = 0x10;
tasks[0][1] = (unsigned int)&first;

tasks[1] = stacks[1] + 256 - 16;
tasks[1][0] = 0x10;
tasks[1][1] = (unsigned int)&task;

Then, call activate with tasks[0] and tasks[1] instead of first_stack_start. Recompile and run, you should see both tasks running in the order that you activate them.

Some abstractions

We’ve hardcoded a bunch of stuff again. We should clean it up so that we don’t have to keep copying these chunks every time we want a new task. Let’s move those magic numbers into constants and make a function to set up a new task:

# STACK_SIZE 256 /* Size of task stacks in words */
# TASK_LIMIT 2   /* Max number of tasks we can handle */

unsigned int *init_task(unsigned int *stack, void (*start)(void)) {
	stack += STACK_SIZE - 16; /* End of stack, minus what we're about to push */
	stack[0] = 0x10; /* User mode, interrupts on */
	stack[1] = (unsigned int)start;
	return stack;

Then, back in main clean up the task initialisation to use these abstractions:

unsigned int stacks[TASK_LIMIT][STACK_SIZE];
unsigned int *tasks[TASK_LIMIT];

tasks[0] = init_task(stacks[0], &first);
tasks[1] = init_task(stacks[1], &task);


Scheduling (deciding what tasks to run, when, and for how long, in a multitasking system) is a big topic. We are going to implement the simplest possible (in our situation) schedule: round-robin. This means that we’ll just activate each task in the order that they were created, and then go back to the beginning and activate each in sequence again.

Since we have no way for tasks to exit, make sure the following is at the end of each task:

while(1) syscall();

This will just cause the task to repeatedly call back into the kernel when it is done.

We’ll also need to keep track in main of how many tasks there are and which one we’re currently running:

size_t task_count = 0;
size_t current_task = 0;

In order to use size_t you’ll need to include stddef.h. Now just make sure that task_count gets set correctly, and replace the code that activates user tasks with this:

while(1) {
	tasks[current_task] = activate(tasks[current_task]);
	if(current_task >= task_count) current_task = 0;

This just activates each task in order, repeatedly, forever. Fairly simple.

You may be wondering why I didn’t use the classic current_task = (current_task + 1) % task_count trick. The reason is that, at least on ARMv6, gcc actually generates a library call for the % operator. You could try linking in libgcc, but there are some problems. For this case, it just wasn’t worth it, and so I’m using an if statement instead.

Code so far on GitHub

Setup for new Syscall

So, our syscall syscall is cute, but it’s not very useful. For good multitasking, we want a way for a user mode task to create new tasks. We’ll do this the way Unix does: fork. This syscall copies the current process, and then returns the ID of the new process to the parent, and 0 to the child.

We need a way for the kernel to know what the user mode task wants it to do. As I mentioned in a previous post, this is what the “argument” to svc is for. We could add code to our context switch to mask the bits off of the end of the svc instruction, but let’s not bother our context switch now. We’re going to store the id of our syscall in a register. syscalls.s is now:

.global syscall
	push {r7}
	mov r7, #
	svc 0
	pop {r7}
	bx lr

.global fork
	push {r7}
	mov r7, #
	svc 0
	pop {r7}
	bx lr

That’s two syscalls, and the context switch will save the new value of r7 on the top of the stack, which we can read in the kernel. The actual value of r7 gets saved and restored by the syscall wrapper.

In order to call our new syscall, we’ll need to add the following to asm.h:

int fork(void);


As you may have guessed, we’re going to implement the fork syscall, in order to make our multitasking more actually useful. To do that, we’re going to need to copy stuff. Because we’re not linking in libc at this point, we need our own memcpy, like so:

void *memcpy(void *dest, const void *src, size_t n) {
	char *d = dest;
	const char *s = src;
	size_t i;
	for(i = 0; i < n; i++) {
		d[i] = s[i];
	return d;


We’re going to use fork to spawn task from first. So, move task up above first, and replace the first call to syscall with:

if(!fork()) task();

Then, modify main so that only first gets set up to run.

The Actual Syscall

So, we’re jumping into the kernel now, but so far we don’t actually do anything with this new syscall. How can we even tell which syscall is being called? Well, remember that the syscall id is in r7 when the context switch happens, so by the time we get to the kernel, we can access it like so:

switch(tasks[current_task][2+7]) {
	case 0x1:

What’s that 2+7 for? Well, remember, we push SPSR and the supervisor mode lr on the top of the stack, so we have to move past those to get to the registers.

Our kernel has a limitation. Specifically, TASK_LIMIT. If we call fork when there is no space for a new task, that would be bad, so we should return an error:

if(task_count == TASK_LIMIT) {
	tasks[current_task][2+0] = -1;
} else {

What are we doing here? We’re changing the saved value of r0, which, you will recall, is the return value of a function. So, we are setting the return value that the user mode task will see to -1.

Now, what does fork actually need to do? It copies all the state from one task into a new one. The new task will need a stack pointer, and said stack pointer will need to be exactly as far from the end of the stack as the current task’s stack pointer:

size_t used = stacks[current_task] + STACK_SIZE - tasks[current_task];
tasks[task_count] = stacks[task_count] + STACK_SIZE - used;

Now we actually have to copy the stack over. Luckily, we know exactly how much to copy, since it’s the same as the distance from the stack pointer to the end:

memcpy(tasks[task_count], tasks[current_task], used*sizeof(*tasks[current_task]));

fork is specified to return the new PID in the parent process, and 0 in the child process:

tasks[current_task][2+0] = task_count;
tasks[task_count][2+0] = 0;

And, finally, we should probably record the fact that there’s a new task:


That’s it!

We now have a multitasking kernel (remember to increase TASK_LIMIT if you want to run more tasks!), and user mode tasks can start new tasks. Next time: hardware interrupts!

Code for this post is on GitHub.