(PART-5) Writing our own Memory Management program for our OS

 

 

 

Introduction

So far, whenever we needed some memory, e.g. to store a string, we allocated it like that: char my_string[10]. This statement tells the C compiler to allocate 10 consecutive bytes in memory that we can use to store our characters.

But what if we do not know the size of the array at compile time? Let's say the user wants to specify the length of the string. We could of course allocate a fixed amount of memory, e.g. 256 bytes. There is a high chance that this is too much, however, effectively wasting memory. Another outcome would be that the statically allocated memory is not enough, making the program crash.

Dynamic memory management can solve this problem. Our OS should offer a way to allocate a flexible amount of memory that is determined at run time. To reduce the risk of running out of memory we also need functionality to make memory available again that is no longer used. In this blog post we want to design and implement a simple algorithm for dynamic memory management.

The remainder of this post is structured as follows. First, we design the data structure that we will use to manage dynamic memory, as well as the allocation and deallocation algorithm. Then, we implement a dynamic memory management for our kernel based on the theory from the previous section.

Design

Data Structure

To implement dynamic memory management, we will statically allocate a large memory region from which individual chunks can be borrowed to parts of our program. When the borrowed memory is no longer needed it can be returned to the pool.

The question is: How do we keep track of the chunks that have been borrowed, i.e. dynamically allocated? We need a data structure that allows us to find available memory of at least the requested size. We also want to pick the smallest possible free region in order to avoid ending up with many small memory fragments. Additionally it would be great if this operation can be performed with minimal effort.

For our simple implementation we will used a doubly linked list. Each element holds information about its chunk, specifically the address and size, whether it is currently allocated, as well as pointers to the previous and next element. We can find the optimal, i.e. the smallest possible, region by iterating through the entire list in O(n), where n is the number of elements in the list. Of course there are more efficient alternatives such as heaps but they are more complex to implement so we are going to stick to the list.

Now where do we store the list? We cannot statically allocate memory for it because we do not know how many chunks will be requested and thus how many elements the list will contain. But we also cannot allocate it dynamically because we are building dynamic memory allocation just now.

We can overcome this problem by embedding the list elements within the large memory region that we reserve for dynamic allocation. For each chunk that is requested we store the respective list element just in front of that chunk. The following figure illustrates the initial state of a 1024 byte dynamic memory region. It contains a single 16 byte list element (the small dark green part in the beginning) indicating that the remaining 1008 bytes are free.

Now let's look into the allocation algorithm.

Allocation Algorithm

When new memory m of size s_m is requested, we go through all available memory looking for an optimal chunk to use. Given our list of memory chunks L, we attempt to find an optimal entry o, such that it is free (free(o)), sufficiently large (s_o ≥ s_m), and there is no smaller entry available (∀x ∈ L: free(x) → s_o ≤ s_x).

Given an optimal segment o, we slice off the requested amount of memory to create a new segment p including a new list entry, effectively shrinking o to size s_o - s_m - s_l, where s_l is the size of a list element. The new segment will have size s_p = s_m + s_l. We then return a pointer to the beginning of the allocated memory, right after the list element. If no optimal chunk exists the allocation is unsuccessful.

The following figure shows the state of the segment list after the algorithm successfully allocated 256 bytes of memory. It contains two elements. The first one refers to a free chunk which takes up 752 bytes of dynamic memory. The second one represents the memory allocated for p1 and takes up the remaining 272 bytes.

Next, we will define an algorithm to free allocated memory.

Deallocation Algorithm

The basic version of the deallocation algorithm is very simple. Given a pointer to an allocated region we obtain the respective list entry by looking at the memory region right in front of it. We then mark the chunk as free so that it will be considered next time new memory is requested.

While this version of the algorithm appears to work it has a major problem: We are creating more and more list entries. This will leave the dynamic memory fragmented, making it harder and harder to allocate larger parts of memory.

To solve this problem we merge the deallocated chunk with all adjacent free chunks. This is where our doubly linked list comes in handy as we can easily determine the previous and the next chunk by following the pointers.

The following animation illustrates a more complex example of different allocations and deallocations of memory.

With the theory covered, let's start implementing the functionality in C so we can use it inside our OS.

Implementation

Doubly Linked List

We will model a chunk of dynamic memory as a struct containing its size (excluding the struct size) and whether it is used (i.e. not free). To make it a doubly linked list we add a prev and a next pointer. Here goes the code.

typedef struct dynamic_mem_node {
    uint32_t size;
    bool used;
    struct dynamic_mem_node *next;
    struct dynamic_mem_node *prev;
} dynamic_mem_node_t;

Next we can initialize the dynamic memory.

Initialization

Before we can allocate dynamic memory we need to initialize it. As described in the design section we are going to start off with a single chunk covering the entire available memory. The following code initializes 4kb of dynamic memory.

#define NULL_POINTER ((void*)0)
#define DYNAMIC_MEM_TOTAL_SIZE 4*1024
#define DYNAMIC_MEM_NODE_SIZE sizeof(dynamic_mem_node_t) // 16

static uint8_t dynamic_mem_area[DYNAMIC_MEM_TOTAL_SIZE];
static dynamic_mem_node_t *dynamic_mem_start;

void init_dynamic_mem() {
    dynamic_mem_start = (dynamic_mem_node_t *) dynamic_mem_area;
    dynamic_mem_start->size = DYNAMIC_MEM_TOTAL_SIZE - DYNAMIC_MEM_NODE_SIZE;
    dynamic_mem_start->next = NULL_POINTER;
    dynamic_mem_start->prev = NULL_POINTER;
}

Let's move on to the implementation of the memory allocation function.

Allocation

Recall from the allocation algorithm definition: First, we look for an optimal memory block. To keep the code readable we create a separate function find_best_mem_block for that part of the algorithm that goes through a given list and returns the smallest free node.

void *find_best_mem_block(dynamic_mem_node_t *dynamic_mem, size_t size) {
    // initialize the result pointer with NULL and an invalid block size
    dynamic_mem_node_t *best_mem_block = (dynamic_mem_node_t *) NULL_POINTER;
    uint32_t best_mem_block_size = DYNAMIC_MEM_TOTAL_SIZE + 1;

    // start looking for the best (smallest unused) block at the beginning
    dynamic_mem_node_t *current_mem_block = dynamic_mem;
    while (current_mem_block) {
        // check if block can be used and is smaller than current best
        if ((!current_mem_block->used) &&
            (current_mem_block->size >= (size + DYNAMIC_MEM_NODE_SIZE)) &&
            (current_mem_block->size <= best_mem_block_size)) {
            // update best block
            best_mem_block = current_mem_block;
            best_mem_block_size = current_mem_block->size;
        }

        // move to next block
        current_mem_block = current_mem_block->next;
    }
    return best_mem_block;
}

We can then use this function to implement our mem_alloc function that takes the requested memory size and returns a pointer to that dynamically allocated memory. It returns a null pointer in case there is no sufficiently large chunk available. Let's look at the code and then go through it step by step.

void *mem_alloc(size_t size) {
    dynamic_mem_node_t *best_mem_block =
            (dynamic_mem_node_t *) find_best_mem_block(dynamic_mem_start, size);

    // check if we actually found a matching (free, large enough) block
    if (best_mem_block != NULL_POINTER) {
        // subtract newly allocated memory (incl. size of the mem node) from selected block
        best_mem_block->size = best_mem_block->size - size - DYNAMIC_MEM_NODE_SIZE;

        // create new mem node after selected node, effectively splitting the memory region
        dynamic_mem_node_t *mem_node_allocate = (dynamic_mem_node_t *) (((uint8_t *) best_mem_block) +
                                                                        DYNAMIC_MEM_NODE_SIZE +
                                                                        best_mem_block->size);
        mem_node_allocate->size = size;
        mem_node_allocate->used = true;
        mem_node_allocate->next = best_mem_block->next;
        mem_node_allocate->prev = best_mem_block;

        // reconnect the doubly linked list
        if (best_mem_block->next != NULL_POINTER) {
            best_mem_block->next->prev = mem_node_allocate;
        }
        best_mem_block->next = mem_node_allocate;

        // return pointer to newly allocated memory (right after the new list node)
        return (void *) ((uint8_t *) mem_node_allocate + DYNAMIC_MEM_NODE_SIZE);
    }

    return NULL_POINTER;
}

We first call the find_best_mem_block function to find the smallest free block. In case there is a block available that we can use, we split it by reducing its size, creating a new node with the requested size at the start of the new chunk and insert it into the list. Finally we return a pointer to the memory address directly after the newly created list node.

We can then use mem_alloc to dynamically allocate an array of n integers and store 1..n inside. Note that thanks to the C compiler we can access the memory using array syntax instead of calculating memory offsets. It will dereference it with the correct offset.

int *ptr = (int *) mem_alloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
    ptr[i] = i+1; // shorthand for *(ptr + i)
}

Now to the mem_free implementation.

Deallocation

The mem_free function takes a pointer to a dynamically allocated memory region. It then loads the respective list node by decrementing the pointer memory address by the node struct size and marks it as free. Finally, it attempts to merge the deallocated memory node with the next and previous list elements. Here you go.

void mem_free(void *p) {
    // move along, nothing to free here
    if (p == NULL_POINTER) {
        return;
    }

    // get mem node associated with pointer
    dynamic_mem_node_t *current_mem_node = (dynamic_mem_node_t *) ((uint8_t *) p - DYNAMIC_MEM_NODE_SIZE);

    // pointer we're trying to free was not dynamically allocated it seems
    if (current_mem_node == NULL_POINTER) {
        return;
    }

    // mark block as unused
    current_mem_node->used = false;

    // merge unused blocks
    current_mem_node = merge_next_node_into_current(current_mem_node);
    merge_current_node_into_previous(current_mem_node);
}

To increase readability we move the merging to separate functions.

void *merge_next_node_into_current(dynamic_mem_node_t *current_mem_node) {
    dynamic_mem_node_t *next_mem_node = current_mem_node->next;
    if (next_mem_node != NULL_POINTER && !next_mem_node->used) {
        // add size of next block to current block
        current_mem_node->size += current_mem_node->next->size;
        current_mem_node->size += DYNAMIC_MEM_NODE_SIZE;

        // remove next block from list
        current_mem_node->next = current_mem_node->next->next;
        if (current_mem_node->next != NULL_POINTER) {
            current_mem_node->next->prev = current_mem_node;
        }
    }
    return current_mem_node;
}

void *merge_current_node_into_previous(dynamic_mem_node_t *current_mem_node) {
    dynamic_mem_node_t *prev_mem_node = current_mem_node->prev;
    if (prev_mem_node != NULL_POINTER && !prev_mem_node->used) {
        // add size of previous block to current block
        prev_mem_node->size += current_mem_node->size;
        prev_mem_node->size += DYNAMIC_MEM_NODE_SIZE;

        // remove current node from list
        prev_mem_node->next = current_mem_node->next;
        if (current_mem_node->next != NULL_POINTER) {
            current_mem_node->next->prev = prev_mem_node;
        }
    }
}

Calling free is straightforward.

int *ptr = (int *) mem_alloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
    ptr[i] = i+1; // shorthand for *(ptr + i)
}
mem_free(ptr);

That concludes the dynamic memory management post :) I think I will pause the FrOS project for a bit now and focus on another project. Maybe I will come back at some point and write a file system or so :D

 

(PART-2) Writing our Video Driver in C Kernel for our OS

 

 

 

Why a VGA Driver?

Our operating system needs some way to interact with the user. This requires us to do some form of I/O. First, we want to focus on visual output. We will rely on the VGA 80x25 text video mode as it is very convenient to handle and flexible enough for basic terminal functionality. This is the same mode that was already used by the BIOS while booting our kernel.

With VGA we can produce screen output by modifying a dedicated memory region, called the video memory, directly. In addition to that, there are specific port addresses that we can use to interact with device ports using the port I/O CPU instructions in and out. This is possible because all I/O ports (including the VGA ports) are mapped to specific memory locations.

The task of our VGA driver will be to encapsulate these low level memory manipulations within higher level functions. Instead of issuing individual CPU instructions and modifying memory addresses we want to be able invoke a function to print a string on the screen or clear all output. In this post we are going to write such a minimal VGA driver.

The remainder of the article is structured as follows. The next section explains how we can interface with I/O ports using C. Afterwards we will put this knowledge to use and implement functions to retrieve and set the text cursor position. Then we will write code to print individual characters on the screen by writing to the video memory. We will combine the cursor manipulation with the character printing to provide functionality for printing strings to the screen. The sections after that focus on a few extensions such as handling newline characters, scrolling, as well as clearing the screen. The final section adjusts the main kernel function to make use of our newly written driver.

The source code is available on GitHub.

Interfacing with I/O Ports from C

One important part of I/O drivers is be the ability to interface with I/O devices through ports. In our VGA driver we only need to access the ports 0x3d4 and 0x3d5 for now, in order to read and set the cursor position while in text mode.

As mentioned earlier, we can utilize the in and out instructions to read and write port data, respectively. But how do we make use of those instructions from within C?

Luckily, the C compiler supports inline assembler code by calling the __asm__ function that lets us write assembler code, passing C variables as input and writing results back into C variables. The assembler instruction, the output parameters, and the input parameters of the __asm__ function are separated by :. The syntax is a bit different compared to NASM, e.g. the order of the instruction operands is reversed.

Let's take a look at the following two functions to read/write data from/to a specified port.

unsigned char port_byte_in(unsigned short port) {
    unsigned char result;
    __asm__("in %%dx, %%al" : "=a" (result) : "d" (port));
    return result;
}

void port_byte_out(unsigned short port, unsigned char data) {
    __asm__("out %%al, %%dx" : : "a" (data), "d" (port));
}

For our port_byte_in function we map the C variable port into the dx register, execute in al, dx, and then store the value of the al register into the C variable result. The port_byte_out function looks similar. It executes out dx, al, mapping the port to dx and the data to al. As we are only writing data there are no output parameters and the function has no return value.

Getting and Setting the Cursor Position

With our newly written port I/O functions we are ready to interact with the VGA text mode cursor. In order to read or change the cursor position we need to modify the VGA control register 0x3d4 and read from or write to the respective data register 0x3d5.

The 16 bit cursor position is encoded as 2 individual bytes, the high and the low byte. The data register will hold the low byte if the control register is set to 0x0f, and the high byte if the value 0x0e is used. First we will define the register addresses and the codes for our offset as C constants.

#define VGA_CTRL_REGISTER 0x3d4
#define VGA_DATA_REGISTER 0x3d5
#define VGA_OFFSET_LOW 0x0f
#define VGA_OFFSET_HIGH 0x0e

We are going to represent our cursor offset as the video memory offset. The memory offset is twice the cursor offset, because each position in the text grid is represented by 2 bytes, one for the character and one for color information.

As we cannot fit a memory offset having twice the size of a 16 bit cursor offset into a 16 bit short, we will use a 32 bit integer. And now we can write a set_cursor and a get_cursor function that takes our internal cursor offset.

void set_cursor(int offset) {
    offset /= 2;
    port_byte_out(VGA_CTRL_REGISTER, VGA_OFFSET_HIGH);
    port_byte_out(VGA_DATA_REGISTER, (unsigned char) (offset >> 8));
    port_byte_out(VGA_CTRL_REGISTER, VGA_OFFSET_LOW);
    port_byte_out(VGA_DATA_REGISTER, (unsigned char) (offset & 0xff));
}

int get_cursor() {
    port_byte_out(VGA_CTRL_REGISTER, VGA_OFFSET_HIGH);
    int offset = port_byte_in(VGA_DATA_REGISTER) << 8;
    port_byte_out(VGA_CTRL_REGISTER, VGA_OFFSET_LOW);
    offset += port_byte_in(VGA_DATA_REGISTER);
    return offset * 2;
}

Note that because our memory offset is double the cursor offset, we have to map the two offsets by multiplying or dividing by 2. We also have to do some bit shifting / masking in order to retrieve the high and the low byte from our integer.

Printing a Character on Screen

Having the cursor manipulations in place, we also need to be able to print characters at a specified position on screen. We already did that in our dummy kernel in the previous post. So let's take that code and make it a bit more generic. First, we will define a few helpful constants containing the starting address for the video memory, the text grid dimensions, as well as a default coloring scheme to use for our characters.

#define VIDEO_ADDRESS 0xb8000
#define MAX_ROWS 25
#define MAX_COLS 80
#define WHITE_ON_BLACK 0x0f

Next, let's write a function to print a character on screen by writing it to the video memory at a given memory offset. We are not going to support different colors for now but we can adjust this later if needed.

void set_char_at_video_memory(char character, int offset) {
    unsigned char *vidmem = (unsigned char *) VIDEO_ADDRESS;
    vidmem[offset] = character;
    vidmem[offset + 1] = WHITE_ON_BLACK;
}

Now that we can print characters on screen and modify the cursor, we can implement a function that prints a string and moves the cursor accordingly.

Printing Text and Moving the Cursor

In C a string is a 0-byte terminated sequence of ASCII encoded bytes. To print a string on the screen we need to:

1. Get the current cursor offset.
2. Loop through the bytes of the string, writing them to the video memory, incrementing the offset.
3. Update the cursor position.

Here goes the code:

void print_string(char *string) {
    int offset = get_cursor();
    int i = 0;
    while (string[i] != 0) {
        set_char_at_video_memory(string[i], offset);
        i++;
        offset += 2;
    }
    set_cursor(offset);
}

Note that this code does neither handle newline characters, nor offsets that are out of bounds at this point. We can fix that by implementing scrolling functionality in case of our offset growing out of bounds, and moving the cursor to the next line when we detect a newline character. Let's look into handling newline characters next.

Handling Newline Characters

A newline character is actually a non-printable character. It does not take space in the grid but instead moves the cursor to the next line. To do that we will write a function that takes a given cursor offset and computes the new offset, which is the first column in the next row.

Before we implement that we will write two small helper functions. get_row_from_offset takes a memory offset and returns the row number of the corresponding cell. get_offset returns a memory offset for a given cell.

int get_row_from_offset(int offset) {
    return offset / (2 * MAX_COLS);
}

int get_offset(int col, int row) {
    return 2 * (row * MAX_COLS + col);
}

Combining those two functions we can easily write the function that moves the offset to the next line.

int move_offset_to_new_line(int offset) {
    return get_offset(0, get_row_from_offset(offset) + 1);
}

With this function at our disposal we can modify the print_string function to handle \n.

void print_string(char *string) {
    int offset = get_cursor();
    int i = 0;
    while (string[i] != 0) {
        if (string[i] == '\n') {
            offset = move_offset_to_new_line(offset);
        } else {
            set_char_at_video_memory(string[i], offset);
            offset += 2;
        }
        i++;
    }
    set_cursor(offset);
}

Next, let's look at how we can implement scrolling.

Scrolling

As soon as the cursor offset exceeds the maximum value of 25x80x2 = 4000 the terminal output should scroll down. Without a scroll buffer the top line will be lost but this is ok for now. We can implement scrolling by executing the following steps:

1. Move all rows but the first one by 1 row upwards. We do not need to move the top row as it would be out of bounds anyway.
2. Fill the last row with blanks.
3. Correct offset to be inside our grid bounds again.

The following animation illustrates the scrolling algorithm.

We can implement the row movement by copying a chunk of the video memory. First, we will write a function that copies a given number of bytes nbytes in memory from *source to *dest.

void memory_copy(char *source, char *dest, int nbytes) {
    int i;
    for (i = 0; i < nbytes; i++) {
        *(dest + i) = *(source + i);
    }
}

With the memory_copy function at our disposal we can implement a scrolling helper function that takes a given offset, copies the desired memory region, clears the last row, and adjusts the offset to be inside the grid bounds again. We will use the get_offset helper method to conveniently determine the offset for a given cell.

int scroll_ln(int offset) {
    memory_copy(
            (char *) (get_offset(0, 1) + VIDEO_ADDRESS),
            (char *) (get_offset(0, 0) + VIDEO_ADDRESS),
            MAX_COLS * (MAX_ROWS - 1) * 2
    );

    for (int col = 0; col < MAX_COLS; col++) {
        set_char_at_video_memory(' ', get_offset(col, MAX_ROWS - 1));
    }

    return offset - 2 * MAX_COLS;
}

Now we only need to modify our print_string function so that each loop iteration it checks if the current offset exceeds the maximum value and scroll if needed. This is the final version of the function:

void print_string(char *string) {
    int offset = get_cursor();
    int i = 0;
    while (string[i] != 0) {
        if (offset >= MAX_ROWS * MAX_COLS * 2) {
            offset = scroll_ln(offset);
        }
        if (string[i] == '\n') {
            offset = move_offset_to_new_line(offset);
        } else {
            set_char_at_video_memory(string[i], offset);
            offset += 2;
        }
        i++;
    }
    set_cursor(offset);
}

Clearing the Screen

After the our kernel has started, the video memory will be filled with some information from the BIOS that is no longer relevant. So we need a way to clear the screen. Fortunately this function is easy to implement given our existing helper functions.

void clear_screen() {
    for (int i = 0; i < MAX_COLS * MAX_ROWS; ++i) {
        set_char_at_video_memory(' ', i * 2);
    }
    set_cursor(get_offset(0, 0));
}

Hello World and Scrolling in Action

We can adjust our main function to print a string now! We only need to include the display header file so our compiler knows that the driver functions exist.

#include "../drivers/display.h"

void main() {
    clear_screen();
    print_string("Hello World!\n");
}

To visualize the scrolling I wrote an extended main function that prints increasing characters, launched QEMU in debug mode, attached the GNU debugger (gdb), put a breakpoint in the print function and executed the following debug instruction to slow down the scrolling so it becomes visible.

while (1)
shell sleep 0.2
continue
end

And this is the result:

Horray! We managed to write a simple, yet working video driver that allows us to print strings on the screen. It even supports scrolling! Next up: Keyboard input :)

 

(PART-4) Writing our own SHELL like MS-DOS

 

 

 

Introduction

Operating systems provide high level functionality to interact with the computer hardware. This functionality needs to be made available to the user in some way, e.g. by a layer around the kernel, exposing simple commands. This outer layer is typically called a "shell".

As we only have a very simple text based VGA driver we will write a command-line shell. Graphical shells are beyond the scope of this series. The remainder of the post is structured as follows.

First, we will implement a key buffer that stores the user input and modify our keyboard callback to fill the buffer in addition to printing on screen. Next, we are going to add backspace functionality so we can correct typos. Thirdly, we will implement a very simple command parsing when the enter key is pressed. Finally, we modify our kernel entry to display a prompt after all initialization work is done.

Key Buffer

Our shell should support complex commands potentially having subcommands and arguments. This means having single key commands is not going to get us very far but we would rather have the user type commands consisting of multiple characters. We need a place to store the command as it is being typed, however. This is where the key buffer comes in.

We can implement the key buffer as an array of characters. It will be initialized with 0 bytes and key presses will be recorded from index 0 upwards. Inspecting this data structure a bit closer you will notice that this is just how we encoded strings. A series of characters, terminated by a 0 byte.

To work with the key buffer efficiently we need two more string utility functions: A function to calculate the length of a string and a function to append a character to a given string. The latter function is going to make use of the former.

int string_length(char s[]) {
    int i = 0;
    while (s[i] != '\0') {
        ++i;
    }
    return i;
}

void append(char s[], char n) {
    int len = string_length(s);
    s[len] = n;
    s[len + 1] = '\0';
}

Next, we can make a few adjustments to our keyboard callback function from the previous post. First, we want to get rid of the humongous switch statement and replace it by an array lookup based on the scan code. Secondly, we ignore all key up and non-alphanumeric scan codes. Lastly, we record each key in the key buffer and output it to the screen.

#define SC_MAX 57

static char key_buffer[256];

const char scancode_to_char[] = {
  '?', '?', '1', '2', '3', '4', '5',
  '6', '7', '8', '9', '0', '-', '=',
  '?', '?', 'Q', 'W', 'E', 'R', 'T',
  'Y', 'U', 'I', 'O', 'P', '[', ']',
  '?', '?', 'A', 'S', 'D', 'F', 'G',
  'H', 'J', 'K', 'L', ';', '\', '`',
  '?', '\\', 'Z', 'X', 'C', 'V', 'B',
  'N', 'M', ',', '.', '/', '?', '?',
  '?', ' '
};

static void keyboard_callback(registers_t *regs) {
    uint8_t scancode = port_byte_in(0x60);

    if (scancode > SC_MAX) return;

    char letter = scancode_to_char[(int) scancode];
    append(key_buffer, letter);
    char str[2] = {letter, '\0'};
    print_string(str);
}

This method works but it has two problems. First, it does not check the boundaries of the key buffer before appending, risking a buffer overflow. Secondly, it does not leave any room for mistakes when typing a command. We will leave fixing the buffer overflow to the reader and implement backspace functionality next.

Backspace

The user should be able to correct typos by pressing backspace, effectively deleting the last character from the buffer and from the screen.

Implementing the buffer modification can be done by reversing the append function. We simply set the last non-0 byte in the buffer to 0. The method will return true if we successfully removed an element from the buffer and false otherwise. Note that you have to import the type definition for bool using #include <stdbool.h>.

bool backspace(char buffer[]) {
    int len = string_length(buffer);
    if (len > 0) {
        buffer[len - 1] = '\0';
        return true;
    } else {
        return false;
    }
}

Printing a backspace character on screen can be implemented by printing an empty character at the position right before the current cursor position and moving the cursor backwards. We will make use of our get_cursor, set_cursor, and set_char_at_video_memory functions from the VGA driver.

void print_backspace() {
    int newCursor = get_cursor() - 2;
    set_char_at_video_memory(' ', newCursor);
    set_cursor(newCursor);
}

To complete the backspace functionality we modify the keyboard callback function by adding a branch specifically for backspace key presses. When backspace is pressed, we first attempt to delete the last character from the key buffer. If this was successful, we also show the backspace on screen. It is important to perform this check because otherwise the user would be able to backspace all the way through the screen without being stopped by prompts.

#define BACKSPACE 0x0E

static void keyboard_callback(registers_t *regs) {
    uint8_t scancode = port_byte_in(0x60);
    if (scancode > SC_MAX) return;

    if (scancode == BACKSPACE) {
        if (backspace(key_buffer)) {
            print_backspace();
        }
    } else {
        char letter = scancode_to_char[(int) scancode];
        append(key_buffer, letter);
        char str[2] = {letter, '\0'};
        print_string(str);
    }
}

Having a key buffer and backspace functionality in place, we can move to the last step: parsing and executing commands.

Parsing and Executing Commands

Whenever the user hits the enter key, we want to execute the given command. That typically involves parsing the command first, potentially splitting it into multiple subcommands, parsing arguments or invoking external functionality. For the sake of simplicity we will only implement very basic "parsing" that checks whether the string is a known command and if it is not, shows an error.

First, we need to write a function to compare two strings. It will go through both strings step by step, comparing the character values. Here goes the code.

int compare_string(char s1[], char s2[]) {
    int i;
    for (i = 0; s1[i] == s2[i]; i++) {
        if (s1[i] == '\0') return 0;
    }
    return s1[i] - s2[i];
}

Next, we have to implement a function execute_command that executes a given command. Our first version of the shell will only recognize a single command called EXIT that halts the CPU. Later we can implement other commands such as rebooting or interacting with a file system. If the command is unknown, we print an error message. Finally, we print a new prompt.

void execute_command(char *input) {
    if (compare_string(input, "EXIT") == 0) {
        print_string("Stopping the CPU. Bye!\n");
        asm volatile("hlt");
    }
    print_string("Unknown command: ");
    print_string(input);
    print_string("\n> ");
}

Finally, we adjust the keyboard callback to move the cursor to the next line, invoke execute_command, and reset the key buffer when the enter key is pressed.

#define ENTER 0x1C

static void keyboard_callback(registers_t *regs) {
    uint8_t scancode = port_byte_in(0x60);
    if (scancode > SC_MAX) return;

    if (scancode == BACKSPACE) {
        if (backspace(key_buffer) == true) {
            print_backspace();
        }
    } else if (scancode == ENTER) {
        print_nl();
        execute_command(key_buffer);
        key_buffer[0] = '\0';
    } else {
        char letter = scancode_to_char[(int) scancode];
        append(key_buffer, letter);
        char str[2] = {letter, '\0'};
        print_string(str);
    }
}

We are almost done! Let's update the main kernel function.

Updated Kernel Function

Actually, there is not much to do. We will clear the screen and display the initial prompt after all initialization work is done and that's it! The updated keyboard handler will do the rest. Here comes the code and a demo!

void start_kernel() {
    clear_screen();
    print_string("Installing interrupt service routines (ISRs).\n");
    isr_install();

    print_string("Enabling external interrupts.\n");
    asm volatile("sti");

    print_string("Initializing keyboard (IRQ 1).\n");
    init_keyboard();

    clear_screen();
    print_string("> ");
}

Amazing, although not very practical until we add new commands :D. In the next post we will add dynamic memory allocation.