Implementation

This section describes the key features of developing an OS for the purpose of implementing Duktape.

Project Compilation

Development Environment Setup

To begin, the following pieces of software are required and can be installed using an Advanced Packaging Tool (APT) such as apt-get:

$ apt-get install build-essentials \
  qemu-system-i386 \
  genext2fs \
  python

This will install the following pieces of software required for the implementation:

• GNU Make (>= 4.1:9.1)
• GCC (>= 4:6.3)
• QEMU for the x86 architecture (>= 2.6)
• GenEXT2FS (>= 1.4)
• Python (= 2.7.X)

Build Procedures for GNU Make

Specifying Source File

Once installation is complete a basic configuration file, Makefile, can be produced and placed the root of the project. This file is used by Make and will hold references to: all the build tools just installed GCC, LD, etc.; testing tools such as QEMU; and, a list of target files, their dependencies, and the task needed to create the target file. A task is a defined as procedure needed to create the target file, consisting of a list of commands executable by the native development environment’s shell. In this implementation, this is typically using GCC to specify an output binary, the target, to compile from a source file, the dependency. For any additional dependencies the target lists, Make will locate its corresponding target.

Instead of executing all the shell commands by hand to compile the relevant source files, Make automates this process. The Makefile should start by laying out essential variables required for the build, for example:

ROOT_DIR      = $(shell pwd)
BUILD_DIR     = $(ROOT_DIR)/build
SRC_DIR       = $(ROOT_DIR)
SUB_DIRS      = kernel
ARCH          = x86
CC            = gcc
CC_FLAGS      = -g -c -m32 -O0 -pedantic
CC_FLAGS     += -std=c99 -nostdinc \
                -fno-builtin -nostartfiles \
                -nodefaultlibs
CC_FLAGS     += -Wall -Wextra -Werror
CC_FLAGS     += -Wno-unused-parameter \
                -fno-stack-protector \
                -finline-functions \
                -Wno-unused-function \
                -fno-stack-protector \
                -ffreestanding
CC_FLAGS     += -I$(SRC_DIR)/kernel/include
LD            = ld
LD_FLAGS      = -m elf_i386 -o kernel.img
QEMU          = /usr/bin/qemu-system-i386
QEMU_ARGS     = -m 256M
GEN_EXT       = genext2fs
GEN_EXT_FLAGS = -q -b 249 ram

All variables ending with _FLAGS are the additional input parameters, or flags, to their respective shell command. In the case of CC_FLAGS, there are an additional 19 parameters. These flags tightly control the compilation of the input source files. A few flags to note are:

• -m32 Controls the maximum bit-length of all variables, addresses, and function addresses.
• -std=c99 -nostdinc -fno-builtin -nostartfiles -nodefaultlibs Tells GCC to use the C99 syntax and to disable all the available libraries and built-in functions it would normally provide to the source. This will be implemented by hand instead.
• -m elf_i386 Forces the linker to aggregate the compiled files for x86 architecture.

In order to easily add target files to the compilation, we can specify methods for additional use such as:

# Import directories for compilation
#
# @param     directory
# @param     files

define import
OBJECTS	     += $(addprefix $(BUILD_DIR)/$(1)/,$(2))
DIRS         += $(1)
endef

# Create a rule
#
# Includes the build rules for a list
# of files in a directory
#
# @param     directory

define createrule
# Compile .c files
$(BUILD_DIR)/$(1)/%.o: $(SRC_DIR)/$(1)/%.c
    @echo -e '\033[1mCompiling $$@...\033[0m'
    $(CC) $(CC_FLAGS) $$< -o $$@
    @echo

# Compile .S files
$(BUILD_DIR)/$(1)/%.o: $(SRC_DIR)/$(1)/%.S
    @echo -e '\033[1mCompiling $$@...\033[0m'
    $(CC) $(CC_FLAGS) $$< -o $$@
    @echo
endef

The defined method import can be used to add the files start.o and main.o from the directory /kernel/boot` like so:

$(eval $(call import,kernel/boot, \
    start.o \
    main.o \
))

Notice how the files specified are listed with the extension .o. This is the target file, and in this case the resulting binary file, which is the result of Make using GCC to compile a set list of source files. For the purpose of the Make method createrule, every target file has only one dependency: it is corresponding source file, either a C file with extension .c or a GNU Assembly file with extension .S. In above example, it main.o depends on main.c only.

Once all the target files have been ‘imported’, the createrule method can be used to go over all the imported files creating the necessary targets and target dependencies like so:

# Create a rule for all the imported files
$(foreach dir, $(DIRS), $(eval $(call createrule,$(dir))))

Finally, the Makefile should end with a target for the resulting bootable image, kernel.img, of the OS and any “phony” targets that are used to help with the build process, such as cleaning up any build files, like so:

all: $(BUILD_DIR) kernel.img

# The target for “everything”
run: all
    $(QEMU) $(QEMU_ARGS) -kernel kernel.img

# Removes build directory and any temp files
clean:
    rm -Rf $(BUILD_DIR)
    rm -f kernel.img

Using Make

Now that a simple Makefile has been specified, the actual program can be used to build all the described source files specified for the implementation. Its basic usage for compiling the standalone OS image is:

$ make all

To test the OS image using QEMU, run:

$ make run

Finally, to remove all the build files created during compilation, the following command can be used:

$ make clean

Kernel

Bootloading

The GRUB Multiboot Specification offers three example files that offer a starting point for the kernel entry. The sample files: multiboot.h; boot.S; and, kernel.c¹, provide the data structures and constants (namely the flags and offsets of the multiboot data structures) required and provided by GRUB; the main method and entry point to the first C file; and, the assembly instructions which set the multiboot flags, set the stack size, and call the main method.

kernel/boot/link.ld

The OS image must be organised in a way which the multiboot flags are positioned at starting address which does not disrupt any previous mappings loaded by the BIOS.² Physical address space above 0x00100000 (1 Mb) is considered safe.

GRUB must receive its mutltiboot flags at the start the kernel base, as this how it recognises the image as valid. To do this, a linker file is used which dictates the positioning of assembly segments. The files provided by GRUB are not useful until compiled and linked together. LD is a tool offered during the installation of GCC which takes the compiled object files and ‘links’ them together. This link can be described by the configuration file detailed below:

OUTPUT_FORMAT(elf32-i386)
ENTRY(start)
physical_addr = 0x00100000;
SECTIONS
{
    . = physical_addr;

    .text physical_addr : AT(physical_addr)
    {
        code = .;
        *(.boot)
        *(.text)
        *(.rodata)
        . = ALIGN(4096);
    }

    .data : AT(physical_addr + (data - code))
    {
        data = .;
        *(.data)
        . = ALIGN(4096);
    }

    .bss : AT(physical_addr + (bss - code))
    {
        bss = .;
        *(.bss)
        . = ALIGN(4096);
    }

    PROVIDE(kernel_end = .);
}

Line 31 of the above code extract describes the end of the multiboot sector and creates a variable, made available to the kernel, as a starting reference to the address of free space available for memory allocation. Finally, an additional Make rule can now be specified in order to automate this link, accepting all the compiled objects and creating the final binary image which represents the OS:

# Build the kernel image
kernel.bin: $(OBJECTS)
    @echo -e '\033[1mGenerating kernel.img...\033[0m'
    $(LD) $(LD_FLAGS) \
      -T $(SRC_DIR)/kernel/boot/linker.ld \
      $(OBJECTS)

Architecture Initialisations

Once compilation of the source files are made seamlessly into a binary image and with the ability to quickly test it using QEMU, the rest of the OS can be implemented. The next steps taken are to initialise components within the realm of the x86 architecture.

kernel/arch/x86/gdt.c

The GDT should be the first component to be initialised, as provisions on access rights and definition of memory regions affects the running of the OS. In order to do this, an array of all the memory regions we wish to define is described. The following snippet illustrates one method of initialising this array, containg: the null segment, kernel code, and kernel data.

gdt_set_gate(SEG_NULL,  0,           0, 0x00000, 0);
gdt_set_gate(SEG_KCODE, STA_X|STA_R, 0, 0xFFFFF, DPL_KERNEL);
gdt_set_gate(SEG_KDATA, STA_W,       0, 0xFFFFF, DPL_KERNEL);

Line 1 describes a null region as this is requested by all x86-based architectures³. Each segment receives 1 GB of storage and has the same starting address and limit. A user segment can be added later on. The method gdt_set_gate has the following interface which sets the necessary bits of the GDT entry:

void set_gdt_gate(segment, _type, _base, _limit, _access);

This method will accept the input parameters and perform the necessary bitwise operations on them for the {access byte and config bits of the GDT segment descriptor. At present it sets the page frame size to 4KB and tells the GDT to use of 32-bit OP-codes by default. This method could be developed further to accept parameters which set these GDT segment in a more sophisticated manner.

The GDT segment can be defined as a C struct following its representation in figure \ref{fig:gdt}:

typedef struct
{
    uint16_t limit_lo;
    uint16_t base_lo;
    uint8_t  base_mid;
    uint8_t  access;
    uint8_t  granularity;
    uint8_t  base_hi;
}
__attribute__((packed)) gdt_entry_t;

The same approach can be taken with GDT register:

typedef struct
{
    uint16_t limit;
    uint32_t base;
}
__attribute__((packed)) gdt_ptr_t;

Once the GDT has been initialised into an array, it must be “flushed” into CPU. This is completed using the OP-code lgdt.

Interrupt Descriptor Table (IDT)

The approach taken to initialise the GDT can be taken with the IDT. The only difference here is the contents of the IDT entry itself. The IDT must contain a reference, or base address, to a particular method. Rather than specifying a reference to the same method in each IDT entry, a unique method can be specified. This unique method will also contain a unique index which identifies the IDT entry itself. Each of these methods can then enter the same common method where additional provisions are taken, such as copying the contents of all the working registers, and calling dynamically allocated methods for a specific interrupt later on by specifying its unique index. This can be implemented in the following manner:

int i;
for(i = 0; i < NUM_IRQ; i++)
	idt_set_gate(i, (uint32_t)irq[0], 0x08, 0x8E);

The unique index is simply an integer starting at 0 and incrementing for the number of IDT entries available. For x86-based architectures there are 256 available interrupts. The first 32 are system critical interrupts which are detected by the processor itself. The rest can be programmed for any use. Once the IDT entries are configured they can be “flushed” to the IDT register using OP-code lidt.

The common method each IDT entry calls should first disable interrupts, calling OP-code cli, followed by passing all the working CPU registers as a parameter, calling OP-code pusha, and Interrupt Stack Gate to a handler which checks if an ISR has been specified. An ISR is a common interface which accepts the working registers as a C struct defined by:

typedef struct
{
    uint32_t ds;
    uint32_t edi;
    uint32_t esi;
    uint32_t ebp;
    uint32_t esp;
    uint32_t ebx;
    uint32_t edx;
    uint32_t ecx;
    uint32_t eax;
    uint32_t intn;
    uint32_t err_num;
    uint32_t eip;
    uint32_t cs;
    uint32_t cflags;
    uint32_t uesp;
    uint32_t ss;
}
isr_reg_t;

The reason for implementing IDTs in this manner is for this common interface. ISRs can be added later on when other devices are detected or user tasks are created, as they may not be present when the OS first initialises.

Memory Management

Once the GDT has been initialised, memory made available in the segments can be put to use. At this point, allocating and retrieving memory in the segment can also provision some elementary protection by the CPU, such as detecting whether the memory is available on a supervisor level or a user level. There is currently no provision for dynamically allocating memory, as it is provided as a linear chunk.

kernel/mem/kmalloc.c

This method will help allocate memory within the segment. Whilst it is not overly sophisticated, it need not be. It serves as a purpose of dividing up the segment into manageable chunks which can be used later on for more sophisticated purposes. The start of the memory is provided by the linker script and can be accessed in the following manner:

extern uintptr_t kernel_end; // Provided by link.ld
uintptr_t memory_location = (uintptr_t)&kernel_end;

With this, providing access to a chunk of memory can be implemented like so:

uintptr_t kmalloc(size_t size)
{
    uintptr_t address = memory_location;
    memory_location += size;
    return address;
}

kernel/mem/pages.c

Paging is initialised by allocating the page directory table using the kmalloc method. This moves the memory location pointer linearly preventing overwrites from occurring should this method be used again. Then, page tables can be set up in sequence for all entries in the page directory table. This same process occurs for actual pages which are configured to into supervisor mode, with the ability to be read and written to, and are “present”. The structures for the page is implemented in the following C structs:

typedef struct page
{
    uint32_t present  : 1;
    uint32_t rw       : 1;
    uint32_t user     : 1;
    uint32_t accessed : 1;
    uint32_t dirty    : 1;
    uint32_t unused   : 7;
    uint32_t frame    : 20;
}
page_t;

typedef struct page_table
{
    page_t pages[NUM_PAGE_TABLES];
}
page_table_t;

typedef struct page_dir
{
    page_table_t *tables[NUM_PAGE_TABLES];
    uintptr_t physical_tables[NUM_PAGE_TABLES];
    uintptr_t physical_address;
}
page_dir_t;

Since all segments have been initialised with the same base address and limit, there is no handling of ‘user space’ and ‘kernel space’.

kernel/mem/brk.c

Aside from procedural functions which do not require access to the CPU, such as memset, sbrk is the first Standard C method to implement. By definition, it is a tool to increase the segment size.⁴ This can be used to dynamically increase the memory were it to fall short of the segment.

void *sbrk(uintptr_t increment)
{
    assert(increment % PAGE_SIZE == 0);
    uintptr_t address = heap_end;
    heap_end += increment;
    uintptr_t i;
    page_t *page;

    for (i = address; i < heap_end; i += PAGE_SIZE)
    {
        page = get_page(kernel_dir, i);

        if(page == 0)
            page = create_page(kernel_dir, i);

        alloc_frame(page, 0, 0);
    }

    heap_end += increment;
    memset((void *)address, 0x0, increment);
    return (void *)address;
}

Duktape

Duktape requires the ability to dynamically allocate memory and this is partially covered through the use of kmalloc.c. However, the bulk of the required functionality comes in the form of mathematical functions such as sin() and cos() and string, procedures such memcopy which make no references to global variables or the CPU ports or registers, despite their names. These are non-standard OS functions which will not be implemented by hand. Instead, using a library such as the Freely Distributable LIBM (FDLIBM) by Sun Microsystems⁵ will provide all the necessary methods.

To include this library in the implementation, it is simply placed in its own subfolder in lib/ where it can be compiled with the -m32 and -D_POSIX flags in order to be compatible with the current implementation. To automate this process, the following can be added to the Makefile:

OBJECTS	     += $(SRC_DIR)/lib/fdlibm/libm.a
CC_FLAGS     += -Llib/fdlibm -Ilib/fdlibm

$(SRC_DIR)/lib/fdlibm/libm.a:
    @echo -e '\033[1mCompiling fdlibm...\033[0m'
    make \
      "CC=gcc" \
      "CFLAGS=-m32 -D_POSIX_MODE -I$(SRC_DIR)/include" \
      -C $(SRC_DIR)/lib/fdlibm/ all

Compiling Duktape

As described in the design, compiling Duktape with the necessary flags compatible with this build operation will result in list of errors describing undefined references to Standard C Libraries. Once all these libraries have been made available with the necessary methods for compilation, the following can be added to the Makefile to automate the build. In a similar fashion to FDLIBM, the following setup assumes the source code to duktape has been placed inside its own subdirectory lib/duktape/:

# Duktape
$(eval $(call import,lib/duktape, \
    duktape.o \
))

CC_FLAGS     += -I$(BUILD_DIR)/lib/duktape

# Duktape configuration (add this to target `all')
duktape:
    @echo -e '\033[1mConfiguring duktape...\033[0m'
    @mkdir -p $(BUILD_DIR)/lib/duktape
    python $(SRC_DIR)/lib/duktape/tools/configure.py \
        --output-directory $(BUILD_DIR)/lib/duktape \
        --architecture $(ARCH) \
        --platform generic \
        --compiler $(CC) \
        -DUK_OPT_NO_FILE_IO
    @rm -f $(BUILD_DIR)/lib/duktape/duktape.o

Executing JavaScript strings

Finally, with all the necessary means for a successful compilation of the Duktape source code, we can include the library, duktape.h, made available during its configuration. Dutkape can thus be implemented in the following manner, executing a string of JavaScript:

duk_context *context = duk_create_heap_default();

if(!context)
    halt("Failed to create a Duktape heap!\n");

// Register global C bindings
duk_push_c_function(context, duk_print, 1);
duk_put_global_string(context, "print");

// Create buffer
char[16] buf = "print('Hello!');";

// Execute buffer
duk_push_lstring(context, buf, sizeof(buf)/sizeof(char));
if (duk_peval(context) != 0) {
    printf("Error: %s\n", duk_safe_to_string(context, -1));
    return;
}
duk_pop(context);

This extract does not include the registration of the method duk_print and is one of the many examples listed in the Duktape Programmers’s Guide⁶. From this point onwards, JavaScript and C can be used together.