Writing a kernel in C and Assembly

One of my goals for a long time was to write a simple standalone kernel in C, just to see if I could.  Well, I finally figured it out, and this is how I did it.

I couldn’t have done this without the tutorials at osdev.org.

I have all the code here hosted at git://github.com/alecrn/kernel.git.

The tools

• Developed on Ubuntu Linux.
• Bochs for testing the kernel.
• NASM version 2.09 to compile assembly files.
• GCC version 4.5.2 to compile C files.
• ld version 2.21 to link the object files.
• GRUB version 0.97 for boot-loading.
• genisoimage to generate the bootable ISO file.

Directory setup

These are the directories in my project directory.

• bin – Compiled binary files.
• obj – Intermediate object files.
• scripts – Scripts and configuration for compiling and testing.
• src – My actual source files.

Loader file

The first file to consider is “loader.s”  This is the assembly code that our bootloader, GRUB, will call to start the kernel going.  It’s basically the glue between the bootloader and our more manageable C code.

global loader
extern kmain

MODULEALIGN equ 1 << 0
MEMINFO     equ 1 << 1
FLAGS       equ MODULEALIGN | MEMINFO
MAGIC       equ 0x1badb002
CHECKSUM    equ -(MAGIC + FLAGS)

section .text
align 4
MultiBootHeader:
    dd MAGIC
    dd FLAGS
    dd CHECKSUM

STACKSIZE equ 0x4000

loader:
    mov esp, stack + STACKSIZE
    push eax
    push ebx

    call kmain

    cli

hang:
    hlt
    jmp hang

section .bss
align 4
stack:
    resb STACKSIZE

This file initializes the stack the kernel will use, and calls “kmain,” which is a function defined in a C file.

The kmain file

#include "clear_screen.h"
#include "write_str.h"

void kmain (void *mbd, unsigned int magic)
{
    if (magic != 0x2badb002)
    {
        // This branch executes if the "magic number" was
        // incorrect, meaning the bootloader failed but kmain was
        // still called.
        return;
    }
    else
    {
        char *bootLoaderName = (char*)((long*)mbd)[16];

        clear_screen();

        write_str(bootLoaderName);
        write_str("\nHello, master.");
    }
}

This is like the kernel equivalent of the “main” function.  Notice the magic number check; the magic number is a particular constant that GRUB will pass to our program.  If the magic number is not what it should be, then something must’ve gone wrong, and we exit.

Otherwise, we can read the bootloader’s name and write some text to the screen.  The clear_screen call, which we will define later, is needed, otherwise all of the text that GRUB displays will be left up.

Next, we call write_str (which we will also define later) to print some text to the screen.

Textual output

To write to the screen, we have to write directly into video memory.  The kernel is, by default, in text mode, which means the video memory is split up into a grid of characters, and you can simply write a character to the right byte and get the corresponding text on the screen.

First of all, I made a file containing some configuration for the video system in video_system.h and video_system.c:

// FILE video_system.h

#ifndef VIDEO_SYSTEM
#define VIDEO_SYSTEM

struct video_system_t
{
    volatile char *pointer;
    int            width;
    int            height;
} video_system;

#endif

// FILE video_system.c

#include "video_system.h"

// Text mode is always 80 columns by 25 rows
struct video_system_t video_system = {(volatile char*)0xb8000, 80, 25};

video_system will contain “pointer,” the pointer to video memory; “width,” the width of the screen in chars; and “height,” the height of the screen in chars.

Video memory is always at 0xb8000, and the width and height are always (as far as I’ve seen) 80 and 25, respectively, in text mode.

Now we can define clear_screen.  To understand how this works, you need to know how video memory is laid out.

Basically, assuming our screen is five by five characters, we could represent it like this:

(1 H) (1 e) (1 l) (1 l) (1 o)
(1 I) (1 a) (1 m) (0 0) (0 0)
(0 0) (0 0) (0 0) (0 0) (0 0)
(0 0) (0 0) (0 0) (0 0) (0 0)
(0 0) (0 0) (0 0) (0 0) (0 0)

Here is the corresponding layout in video memory:

1H1e1l1l1o1I1a1m0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Each spot on the screen is represented by two bytes, of which the left one is the color and the right is the character.

Knowing just that, we can write clear_call:

// FILE clear_screen.h

#ifndef CLEAR_SCREEN
#define CLEAR_SCREEN

void clear_screen ();

#endif

// FILE clear_screen.c

#include "clear_screen.h"
#include "video_system.h"

void clear_screen ()
{
    volatile char *video = video_system.pointer;
    int            i;

    for (i = 0; i < video_system.width * video_system.height * 2; i += 2)
    {
        video[i]     = ' ';
        video[i + 1] = 0x00;
    }
}

So this procedure simply runs through each of the (width × height × 2) bytes in video memory, setting the color to 0 (black) and the character to a space.

Now that we’ve cleared the screen, we need to be able to put characters and colors in the correct spots.  Before we write the code that places a character into video memory, we should define a system for creating colors.

A color, as above, is a single byte, although it is split up into two colors:  A foreground and background color, each of which has a three-bit color indicator (black, white, blue, etc.) and a one-bit brightness indicator (1 means bright, 0 means dim).

// FILE color.h

#ifndef COLOR
#define COLOR

typedef unsigned char color_t;

enum color_e
{
    BLACK = 0,
    BLUE,
    GREEN,
    CYAN,
    RED,
    MAGENTA,
    BROWN,
    WHITE
};

color_t make_color (int fore, int fore_bright, int back, int back_bright);

#endif

// FILE color.c

#include "color.h"

color_t make_color (int fore, int fore_bright, int back, int back_bright)
{
    fore_bright &= 1; // Make sure they're only 1 or 0
    back_bright &= 1;

    return (back_bright << 7) | (back << 4) | (fore_bright << 3) | fore;
}

Now we can write a function, put_char, that places a character with a color at a given row and column on the screen:

// FILE put_char.h

#ifndef PUT_CHAR
#define PUT_CHAR

#include "color.h"

void put_char (char c, color_t color, int row, int col);

#endif

// FILE put_char.c

#include "put_char.h"
#include "video_system.h"

void put_char (char c, color_t color, int row, int col)
{
    volatile char *video = video_system.pointer;
    int            index = 2 * ((row * video_system.width) + col);

    video[index]     = c;
    video[index + 1] = color;
}

Another concern is writing characters one-by-one after the other, which is important in writing strings.  To do that, the program must remember where it put the last character.  I did this using a cursor structure:

// FILE write_cursor.h

#ifndef WRITE_CURSOR
#define WRITE_CURSOR

#include "color.h"

struct write_cursor_t
{
    int     row, col;
    color_t color;
} write_cursor;

#endif

// FILE write_cursor.c

#include "write_cursor.h"

// Initialize cursor to position (0, 0) and white on black
struct write_cursor_t write_cursor = {0, 0, 0x0f};

Next, we’ll write a write_char functions that uses put_char and write_cursor together so that successive calls will write characters in order:

// FILE write_char.h

#ifndef WRITE_CHAR
#define WRITE_CHAR

void write_char (char c);

#endif

// FILE write_char.c

#include "write_char.h"
#include "put_char.h"
#include "write_cursor.h"
#include "video_system.h"

void write_char (char c)
{
    // Break at a newline
    if (c == '\n')
    {
        write_cursor.col = 0;
        write_cursor.row += 1;

        return;
    }

    put_char(c, write_cursor.color, write_cursor.row, write_cursor.col);

    write_cursor.col += 1;

    // Wrap at right edge of screen
    if (write_cursor.col >= video_system.width)
    {
        write_cursor.col = 0;
        write_cursor.row += 1;
    }
}

Finally, it will now be trivial to write the write_str function:

// FILE write_str.h

#ifndef WRITE_STR
#define WRITE_STR

void write_str (const char *str);

#endif

// FILE write_str.c

#include "write_str.h"
#include "write_char.h"

void write_str (const char *str)
{
    int i;

    for (i = 0; str[i] != ''; ++i)
    {
        write_char(str[i]);
    }
}

And that’s all as far as code!  You now have enough to make a kernel with basic output abilities.  I’ll leave keyboard input up to you (hint).

Compiling

Now, we have to compile the code.

First, we need to configure ld to properly link the object files so that GRUB can find our kernel.  This is the file “scripts/linker.ld”:

ENTRY (loader)

SECTIONS {
    . = 0x00100000;

    .text : {
        *(.text)
        *(.rodata*)
        *(.rdata*)
    }

    .rodata ALIGN (0x1000) : {
        *(.rodata)
    }

    .data ALIGN (0x1000) : {
        *(.data)
    }

    .bss : {
        sbss = .;
        *(COMMON)
        *(.bss)
        ebss = .;
    }
}

We can also make a menu file, “scripts/menu.lst,” for GRUB to show when we boot up:

default 0
title MyOS
kernel /boot/kernel.bin

This is what my compilation script, scripts/compile.sh, looks like:

# Display error message $1 and exit with code $2
function failure () {
    echo $1
    exit $2
}

# Return all sources suffixed by $1
function sources () {
    echo ../src/*$1
}

# Directories we'll use
src=../src
obj=../obj
bin=../bin

# Clean the object and binary directories
rm $obj/* 2>/dev/null
rm $bin/* 2>/dev/null

# Assemble assembly files (output placed in .)
for file in `sources .s`
    do nasm -f elf $file || failure 'Assembly failed' 1
done

echo 'Assembly successful.'

# Compile all C files to object files (output placed in same directory as C file)
gcc -c `sources .c` -Wall -Wextra -Werror -nostdlib -nostartfiles -nodefaultlibs || failure 'Compilation failed' 2

echo 'Compilation successful.'

# Move object files to their proper place
mv *.o `sources .o` ../obj

# Link the files
ld -T ../ld/linker.ld -o $bin/kernel.bin $obj/*.o || failure 'Link failed' 3

echo 'Linking successful.'

./make-image.sh

echo 'Done.'

The previous script calls another script, make_image.sh, which is responsible for taking the compiled kernel and placing it in an ISO CD image (note that it uses genisoimage and requires that you completed the included tutorial):

bin=../bin
isofiles=$bin/isofiles
grub=../grub

mkdir -p $isofiles/boot/grub
cp /usr/lib/grub/i386-pc/stage2_eltorito $isofiles/boot/grub
cp $grub/menu.lst $isofiles/boot/grub
cp $bin/kernel.bin $isofiles/boot
genisoimage -R -b boot/grub/stage2_eltorito -quiet -no-emul-boot \
            -boot-load-size 4 -boot-info-table \
            -o $bin/os.iso $isofiles

Here’s a configuration file for Bochs (place it in scripts/bochsrc.txt):

boot: cdrom
ata0: enabled=1, ioaddr1=0x1f0, ioaddr2=0x3f0, irq=14
ata0-master: type=cdrom, path="../bin/os.iso", status=inserted

And finally, a test script to load our kernel into Bochs and run it:

bochs -f bochsrc.txt

I hope that works for you, and that you have less pain than I did.  If this code doesn’t work for you, I’d like to hear about it (I might even be able to fix it!).

7 things I wish I knew learning PHP

Way back in 2009, I decided that my friends and I, who hoped one day to be game design entrepreneurs, needed a web site.  I knew a bit of HTML, so naturally, I decided I would make it.

Looking back, I don’t know how I made that decision, but over a few weeks I found myself diving in headfirst learning CSS and PHP.  Over time, I’ve found a few tips I wish I could’ve passed to my younger, slightly experienced self.

1. String and array manipulations

PHP has a great variety of string functions and array functions.  There are some particular ones I wish I knew about.

• explode and implode - Explode splits a string into an array with a delimiter, and implode does the opposite.  Examples:

  explode(',', 'Comma,delimited,list')
    => array('Comma', 'delimited', 'list')
  
  implode(', ', array('a', 'item 2', 'hello'))
    => array('a, item 2, hello')
  
  array_map(trim, explode(',', "1, 2, 3,   4,5, \n\t twenty 6,7"))
    => array('1', '2', '3', '4', '5', 'twenty 6', '7') 

• crypt - A handy and quick way to encrypt a string.  Note that this is a one-way encryption.
• trim - Clean whitespace from the beginning and end of a string.  It also has two variants, ltrim and rtrim, which clean whitespace from only the beginning or end of the list, respectively.
• $a[] - Compact syntax for appending an element.  Basically, the following are all equivalent:

  $a[] = 5;
  
  $a[count($a) - 1] = 5;
  
  array_push($a, 5);

It’s also very handy to learn regular expressions.  Cats who Code has a helpful article on some common regular expressions.

There are a few others worth mentioning, but check the reference pages and you’ll probably find what you’re looking for.

2. filter_var and htmlspecialchars

filter_var allows you to test and sanitize a string according to some predefined format.  For example, you can use it to check if an e-mail address or number given by a user is valid and also clean it up at the same time (ex. “Number -5″ would be sanitized to “-5,” then checked to see if it’s a valid number).

While filter_var filters input, htmlspecialchars filters output.  You should use it anytime you print text into an HTML document that might contain angle brackets or other characters that can interfere with HTML.

3. PDO

PHP Data Objects, or PDO, provide an abstract interface for SQL databases, like MySQL, PostgreSQL, MySQL, et al.  Here’s an example of connecting to an SQLite database:

try
{
    $pdo = new PDO('sqlite:test.sqlite3');

    $query = 'SELECT name, color, calories
              FROM   fruit
              WHERE  calories < :calories OR color = :color
             ';

    $statement = $pdo->prepare($query);

    $statement->execute(array(
        'calories' => 500,
        'color'    => 'Orange'
    ));

    $fruits = $statement->fetchAll();

    foreach ($fruits as $fruit)
    {
        echo $fruit['name'], '<br>';
    }
}
catch (PDOException $e)
{
    echo 'Database error: ', $e->getMessage();
}

4. SQLite

SQLite is very useful, as it requires almost no configuration, and since the databases are stored in files, they’re easy to manipulate and move.  Also, if a very common action is opening a database to select some values, like configuration values or the like, SQLite has extremely fast selection speed.

I’m not encouraging SQLite as a superior alternative to a database system like PostgreSQL, but instead as a lightweight and rich data storage and retrieval tool.  On a side note, if you’re using PDO, transitioning from one database to another is painless (so plus one for PDO!).

5. How switching in and out of PHP blocks works

When I began programming in PHP, I assumed that the following code would not work:

<?php
    $x = array(1, 2, 3);

    if (count($x) == 3):
?>
X has three elements.
<?php
    endif;

    echo count($x);
?>

First, I assumed that you couldn’t end a control structure in one PHP block and finish it in another, and I also thought that $x would go out of scope and not be there in the second block.

Later, I realized that PHP is basically a very output-oriented language.  Essentially, the following is “Hello, world!” in PHP:

Hello, world!

I have yet to find a more concise and compact way to express output in a programming language, and that’s PHP’s purpose.  I thought the engine would pick out PHP blocks and execute them, replacing them each as indivisible blocks of code.  I now understand that the code example I showed earlier is more like this:

<?php
    $x = array(1, 2, 3);

    if (count($x) == 3)
    {
       echo 'X has three elements.';
    }

    echo count($x);

6. Capturing output

It turns out you can capture the standard output resulting from executed PHP code using ob_start and its related functions.  Here’s an example:

echo 'Hello, world!<br>';

ob_start();
  echo 'This output will be captured.<br>';

  ob_start();
    echo 'This output will be captured in a nested manner.<br>';

    $out1 = ob_get_contents();

    echo 'There were ', strlen($out1), ' characters in the string ', $out1, '<br>';
  ob_end_flush();

  echo 'This output will also be captured.<br>';

  $out2 = ob_get_contents();
ob_end_clean();

echo 'I will now print the contents of out2: ';
echo $out2;

Would result in:

Hello, world
I will now print the contents of out2:
This output will be captured.
This output will be captured in a nested manner.
There were 48 characters in the string "This output will be captured in a nested manner."
This output will also be captured.

This is particularly useful with functions that always write to standard output, like var_dump, and you want to somehow manipulate or store its output.

7. Coalescing, error-suppressing, and lazily evaluating operators

A common source of errors and unreliability of PHP programs could probably be contributed to laziness.  It is so easy to just take an invalidated number input and go with it or not check for empty values.

The first operator is the coalescing operator, ?:, which simply takes, on the left, a possibly empty value, and on the right, a default.  If the possibly empty value is false, null, etc. the result of the expression will be the right hand value; otherwise, it will be the left hand value.

The error-suppression operator, @, also affectionately called the shut-up operator, suppresses pesky warnings from evaluating an expression.  If you’re tempted to use it, you should first consider fixing the error in the first place, but I find it useful when something’s default value (like how accessing a nonexistent array key returns null) is what I want.

Lazy evaluation (also called non-strict evaluation, as opposed to eager or strict evaluation) refers to not evaluating something until strictly necessarily.  For example, if you have “True or ?,” you can tell the result must be True, no matter what ? is.  In PHP’s case, the ? wouldn’t even be evaluated.  Similarly, “False and ?” would always be False, so ? wouldn’t be evaluated.

I was pleased to find the previous three operators because it makes providing defaults and making robust code more convenient, which means I’m more likely to develop good habits.  Here’s an example, also including some logical operator tricks:

is_array($a) or die('$a is not an array!  Terminating program.');

($b == 0) and die('$b is equal to 0!  Terminating program.');

@$_GET['page'] ?: 'If $_GET[page] is not defined, I will be returned.';

foreach (@$a ?: array() as $v) {
    echo 'If $a is false, null, or undefined, it will be as though it contained an empty array.';
}

This makes it easier to have good habits, since error checking is less of a pain.

Learning a programming language

I recently took my first computer science class, and was interested to see how my classmates handled learning Java, which was, for many of them, their first programming language.

I had already been programming for a few years, and was always glad to help the others.  As expected, the most common mistake was syntax, like forgetting a brace, type, or semicolon.  They also hadn’t yet learned to read compiler errors, causing me to become an expert in leaving my chair.  Beyond that, the main obstacle was thinking in the procedural style so they could answer the critical question, “How do I say that?”

I think the class would’ve been more successful if we started with a language like Python.  I’ve always wondered whether having a first language with types was a good or bad thing, but I think Python’s intuitive style would be a great benefit.

What makes more sense to a beginning programmer?

public class Main
{
    public static void main (String[] args)
    {
        System.out.println("Hello, world!");
    }
}

Or:

print('Hello, world!')

The main problem with the first is the illusion of complexity.  It is a very simple program, yet the sudden suffusion of alien syntax, words, and operators obscures the true meaning:  Print “Hello, world!”  To really understand the whole of it, one must know classes, access specifiers, static methods, types, and object-method dereferencing.

Language learning seems to rely on moving mechanisms from our frontal lobe into their better-suited locations.  Imagine how difficult it would be to speak if you had to consciously think about moving your mouth and tongue, and simultaneously construct the grammar for your sentences out of conceptual goop!  In the same way, a programmer has to fluidly identify the real problem they’re trying to solve, formulate a solution, translate it into a given language, and type it, often all at the same time.  It seems a bit harsh to ask beginning programmers to learn such a heavy-handed syntax before learning how to think like a programmer.

A common issue I noticed with the students and syntax was learning how to manipulate data structures.  Consider the following for-loop in Java:

for (int i = 0; i < 10; ++i)
{
    System.out.println(i);
}

with this Python equivalent:

for i in range(10):
    print(i)

Because too much time was being spent learning how to make a for-loop and wondering why programs including one didn’t work properly, it took too long for the students to grasp a deep intuition of how to represent and transverse data, and, sadly, some never really did.

All in all, I think we (or at least I) would’ve appreciated the class more had we learned Python first.  I’ll just keep solace in the idea I might teach a programming class someday.