Tic Tac Toe Kernel

Tic Tac Toe Kernel is a project I created with Valyreon in June of 2018, that has helped us gain better understanding of Kernel development. It provides users with an opportunity to engage in a game of Tic Tac Toe against the Kernel at two different difficulty levels: easy and hard. At the hard level, the Kernel is impossible to beat, making the best case scenario a draw game, while the easy level is made in such a way that the Kernel is playing the first free board space, thus making it easy to gain a win over the Kernel.

Tic Tac Toe Kernel easy gameplay running on Oracle VM VirtualBox

Table of contents

• Tic Tac Toe Kernel
  • Table of contents
  • Introduction
  • Requirements
  • Tic Tac Toe Gameplay
  • Kernel
    • Link file
    • Boot code
    • Global Functions
    • Monitor code
      • Moving the cursor
    • GDT and IDT
      • The Global Descriptor Table
      • The Interrupt Descriptor Table
    • Booting the kernel
      • Build a binary file
      • Building a bootable image
    • OS testing
  • References
    • Books
    • Links
  • Screenshots
  • To-Do List

Introduction

The idea behind this project was to develop a simple, beginner-friendly, UNIX-clone operating system for the x86 architecture. The created OS is monolithic as this was the path of the least resistance while programming. Because of the aforementioned reasons, this is a very simple kernel because the used algorithms are not optimal or uttermost space efficient. The goal with this project was to gain basic knowledge on the kernel development and not to write the most efficient kernel possible. By writing this, a hope I will inspire someone to write their own kernel. Because of the extensible nature of this kernel, you could use the provided code and easily build your kernel on top of this one.

Note

• The first part of this README will focus on the explanation of the kernel development, while the second part will focus on the Tic Tac Toe game and the Decision Tree.

• The provided code contains a lot of comments, so if something isn't explained in README it is probably explained in the source code.

Requirements

To compile and run this code you will need Linux, GCC, LD, GNU MAKE, NASM and QEMU. In order to fully understand everything that is written in this project, you will need to have a very good knowledge of C and a pretty good understanding of assembly (Intel syntax) as well as some basic knowledge of registers. Knowledge of Linux will be very helpful as the scripts and tutorial is tailor for it.

Tic Tac Toe Gameplay

...

Kernel

Link file

This file tells LD (GNU Linker) how to set up our kernel image. For more information about the LD check out this link. Firstly, it tells that the start location of our binary should be the symbol start. The .text section, the place where our code goes, should be first and should start at 0x100000 or 1 MB. The .data section should be next, followed by the .bss section, while each should be page-aligned with ALIGN(4K).

Note: The linker script specifies start as the entry point to the kernel and the bootloader will jump to this position once the kernel has been loaded.

Boot code

To start your OS we will an existing piece of software to load it. This is called bootloader and we have used GRUB as the goal of this project wasn't to develop our own bootloader. Unless you really want to develop a bootloader, I recommend using one of the already available bootloaders. The boot.s is a Kernel start location which also defines multiboot header. Multiboot Standard describes an interface between the bootloader and the OS kernel, so we don't have to worry about that. It works by putting some magic values in some global variables inside the multiboot header.

tic-tac-toe-kernel/boot.s

Lines 10 to 14 in 1e8b7d2

	section .multiboot
	align 4
	dd MAGIC
	dd FLAGS
	dd CHECKSUM

When the bootloader sees these values, it recognizes the kernel as multiboot compatible, and it knows how to load us, and it can even forward us important information. Since there is no stack yet, we need to make sure the global variables are set correctly.

tic-tac-toe-kernel/boot.s

Lines 2 to 6 in 1e8b7d2

	MBALIGN equ 1 << 0 ; align loaded modules on page boundaries
	MEMINFO equ 1 << 1 ; provide memory map
	FLAGS equ MBALIGN | MEMINFO ; this is the Multiboot 'flag' field
	MAGIC equ 0x1BADB002 ; 'magic number' lets bootloader find the header
	CHECKSUM equ -(MAGIC + FLAGS) ; checksum of above, to prove we are multiboot

The Multiboot Standard doesn't define the value of the stack pointer register ESP, and it is up to the kernel to provide a stack. We allocate room for a small stack by creating a symbol at the bottom of it (stack_bottom), allocating x amount of bytes and finally creating a symbol at the top (stack_top).

mov esp, stack_top

To set up a stack, we set the ESP register to point to the top of the stack. This is very important, as a program written in C cannot function without a stack. After which we put the computer into an infinite loop. We achieve this by:

1. Disabling interrupts with cli (clear interrupt enable in eflags).
2. Waiting for the next interrupt to arrive with hlt.
3. Jumping to the hlt instruction if it ever wakes up due to a non-maskable interrupt occurring or due to system management mode.

Warning

• The stack on x86 must be 16-byte aligned.

• The stack grows downwards on x86.

• The compiler will assume the stack is properly aligned and failure to align the stack will result in undefined behavior.

• CHECKSUM field is defined such that when the magic number, the flags and this are added together, the total must be zero. It is for error checking.

Global Functions

We have defined few commonly-used global functions inside the common.c and common.h. They contain function for writing to and reading from the I/O bus, strcmp, strcpy and strcat functions.

Monitor code

Moving the cursor

First we calculate a linear offset of the $(x,y)$ cursor coordinate, after which we send this offset to the VGA controller that accepts the 16-bit location as two bytes.

GDT and IDT

The GDT and the IDT are descriptor tables. They are arrays of flags and bit values describing the operation of either the segmentation system (in the case of the GDT), or the interrupt vector table (IDT).

The Global Descriptor Table

The Global Descriptor Table (GDT) is a table in memory that defines the processor's memory segments. The GDT sets the behavior of the segment registers and helps to ensure that protected mode operates smoothly. Segmentation is built into the x86 architecture, and it's impossible to get around it. With segmentation, every memory access is evaluated with respect to a segment. That is, the memory address is added to the segment's base address, and checked against the segment's length. The GDT is pointed to by a special register in the x86 chip, the GDT Register, or simply the GDTR. The GDTR is 48 bits long. The lower 16 bits tell the size of the GDT, and the upper 32 bits tell the location of the GDT in memory.

tic-tac-toe-kernel/gdt.s

Lines 3 to 15 in 1e8b7d2

	gdt_flush:
	mov eax, [esp+4] ; Get the pointer to the GDT, passed as a parameter.
	lgdt [eax] ; Load the new GDT pointer
	mov ax, 0x10 ; 0x10 is the offset in the GDT to our data segment
	mov ds, ax ; Load all data segment selectors
	mov es, ax
	mov fs, ax
	mov gs, ax
	mov ss, ax
	jmp 0x08:.flush ; 0x08 is the offset to our code segment: Far jump!
	.flush:
	ret

Keep in mind that the GRUB sets a GDT up for you. The problem is that you don't know where that GDT is, or what's in it. So you could accidentally overwrite it. There are total of 6 segmentation registers (cs, ds, es, fs, gs and ss). Each holds an offset into the GDT. The GDT table contains a number of entries called Segment Descriptors. Each is 8 bytes long and contains information on the starting point of the segment, the length of the segment, and the access rights of the segment.

tic-tac-toe-kernel/include/descriptor_tables.h

Lines 9 to 17 in 1e8b7d2

	struct gdt_entry_struct
	{
	u16int limit_low; // The lower 16 bits of the limit.
	u16int base_low; // The lower 16 bits of the base.
	u8int base_middle; // The next 8 bits of the base.
	u8int access; // Access flags, determine what ring this segment can be used in.
	u8int granularity;
	u8int base_high; // The last 8 bits of the base.
	} __attribute__((packed));

The Interrupt Descriptor Table

The Interrupt Descriptor Table (IDT) is a data structure used by the x86 architecture to implement an interrupt vector table. The IDT is used by the processor to determine the correct response to interrupts and exceptions.

Three general interrupt and exceptions sources:

• Exceptions
• Software interrupts
• External interrupts

Types of Exceptions:

• Faults - are precise exceptions reported on the boundary before the instruction causing the exception.
• Traps - are precise exceptions reported on the boundary following the instruction causing the exception.
• Aborts - are imprecise exceptions. Because they are imprecise, aborts typically do not allow reliable program restart.

Like the GDT the IDT is an array of 8-byte descriptors. Unlike the GDT the first entry of the IDT may contain a descriptor. It is just an array of entries, each one corresponding to an interrupt number. There are 256 possible interrupt numbers, so 256 must be defined. If an interrupt occurs and there is no entry for it (even a NULL entry is fine), the processor will panic and reset. The processor will sometimes need to signal your kernel. Something major may have happened, such as a divide-by-zero, or a page fault. To do this, it uses the first 32 interrupts. The special CPU-dedicated interrupts are shown below.

0	Division by zero exception
1	Debug exception
2	Non maskable interrupt
3	Breakpoint exception
4	Overflow
5	Out of bounds exception
6	Invalid opcode exception
7	No coprocessor exception
8	Double fault
9	Coprocessor segment overrun
10	Invalid Task State Segment
11	Segment not present
12	Stack Segment Fault
13	General Protection Fault
14	Page fault
15	Reserved
16	x87 Floating Point Exception
17	Alignment check exception
18	Machine check exception
19-31	Reserved

Booting the kernel

If you don't want to build your own bootable image, download the latest release of the Kernel and head over to OS testing section.

Build a binary file

Move the build.sh file to a src/ directory and then simply run the build script as:

sh ./src/build.sh

This will produce a binary file kernel.bin.

Building a bootable image

You can create a bootable image containing the GRUB bootloader and your kernel using the program grub-mkrescue.

To create a bootable image, run in the following commands:

mv kernel.bin isodir/boot/kernel.bin
grub-mkrescue -o KernelXO.iso isodir

OS testing

After installing QEMU use the following command to start the KernelXO.iso:

qemu-system-x86_64 -cdrom KernelXO.iso

Alternatively, you could mount the ISO image to a Virtual Machine.

References

Books

• Intel® 64 and IA-32 Architectures Software Developer’s Manual

• Tu, Do Hoang - Operating System: From 0 to 1

Links

• osdev.org wiki

• Kernel Structures

• GCC Cross-Compiler

• x86 Assembly/X86 Architecture

• Expected errors while building a cross compiler

• OSDev.org Tutorial: Build an i686-elf Cross Compiler under 64-bit Ubuntu Desktop 16.04.1

Screenshots

Here are some kernel screenshots:

Tic Tac Toe Kernel running using QEMU

To-Do List

• Complete the README.md
• Implement shutdown
• Implement score restart
• Implement gameplay restart