diff options
Diffstat (limited to 'doc/littleosbook.github.io.txt')
| -rw-r--r-- | doc/littleosbook.github.io.txt | 3261 |
1 files changed, 3261 insertions, 0 deletions
diff --git a/doc/littleosbook.github.io.txt b/doc/littleosbook.github.io.txt new file mode 100644 index 0000000..4600b11 --- /dev/null +++ b/doc/littleosbook.github.io.txt @@ -0,0 +1,3261 @@ +The little book about OS development + +Erik Helin, Adam Renberg + + [1]2015-01-19 | Commit: fe83e27dab3c39930354d2dea83f6d4ee2928212 [2]PDF + version + +Contents + + * [3]1 Introduction + + [4]1.1 About the Book + + [5]1.2 The Reader + + [6]1.3 Credits, Thanks and Acknowledgements + + [7]1.4 Contributors + + [8]1.5 Changes and Corrections + + [9]1.6 Issues and where to get help + + [10]1.7 License + * [11]2 First Steps + + [12]2.1 Tools + o [13]2.1.1 Quick Setup + o [14]2.1.2 Programming Languages + o [15]2.1.3 Host Operating System + o [16]2.1.4 Build System + o [17]2.1.5 Virtual Machine + + [18]2.2 Booting + o [19]2.2.1 BIOS + o [20]2.2.2 The Bootloader + o [21]2.2.3 The Operating System + + [22]2.3 Hello Cafebabe + o [23]2.3.1 Compiling the Operating System + o [24]2.3.2 Linking the Kernel + o [25]2.3.3 Obtaining GRUB + o [26]2.3.4 Building an ISO Image + o [27]2.3.5 Running Bochs + + [28]2.4 Further Reading + * [29]3 Getting to C + + [30]3.1 Setting Up a Stack + + [31]3.2 Calling C Code From Assembly + o [32]3.2.1 Packing Structs + + [33]3.3 Compiling C Code + + [34]3.4 Build Tools + + [35]3.5 Further Reading + * [36]4 Output + + [37]4.1 Interacting with the Hardware + + [38]4.2 The Framebuffer + o [39]4.2.1 Writing Text + o [40]4.2.2 Moving the Cursor + o [41]4.2.3 The Driver + + [42]4.3 The Serial Ports + o [43]4.3.1 Configuring the Serial Port + o [44]4.3.2 Configuring the Line + o [45]4.3.3 Configuring the Buffers + o [46]4.3.4 Configuring the Modem + o [47]4.3.5 Writing Data to the Serial Port + o [48]4.3.6 Configuring Bochs + o [49]4.3.7 The Driver + + [50]4.4 Further Reading + * [51]5 Segmentation + + [52]5.1 Accessing Memory + + [53]5.2 The Global Descriptor Table (GDT) + + [54]5.3 Loading the GDT + + [55]5.4 Further Reading + * [56]6 Interrupts and Input + + [57]6.1 Interrupts Handlers + + [58]6.2 Creating an Entry in the IDT + + [59]6.3 Handling an Interrupt + + [60]6.4 Creating a Generic Interrupt Handler + + [61]6.5 Loading the IDT + + [62]6.6 Programmable Interrupt Controller (PIC) + + [63]6.7 Reading Input from the Keyboard + + [64]6.8 Further Reading + * [65]7 The Road to User Mode + + [66]7.1 Loading an External Program + o [67]7.1.1 GRUB Modules + + [68]7.2 Executing a Program + o [69]7.2.1 A Very Simple Program + o [70]7.2.2 Compiling + o [71]7.2.3 Finding the Program in Memory + o [72]7.2.4 Jumping to the Code + + [73]7.3 The Beginning of User Mode + * [74]8 A Short Introduction to Virtual Memory + + [75]8.1 Virtual Memory Through Segmentation? + + [76]8.2 Further Reading + * [77]9 Paging + + [78]9.1 Why Paging? + + [79]9.2 Paging in x86 + o [80]9.2.1 Identity Paging + o [81]9.2.2 Enabling Paging + o [82]9.2.3 A Few Details + + [83]9.3 Paging and the Kernel + o [84]9.3.1 Reasons to Not Identity Map the Kernel + o [85]9.3.2 The Virtual Address for the Kernel + o [86]9.3.3 Placing the Kernel at 0xC0000000 + o [87]9.3.4 Higher-half Linker Script + o [88]9.3.5 Entering the Higher Half + o [89]9.3.6 Running in the Higher Half + + [90]9.4 Virtual Memory Through Paging + + [91]9.5 Further Reading + * [92]10 Page Frame Allocation + + [93]10.1 Managing Available Memory + o [94]10.1.1 How Much Memory is There? + o [95]10.1.2 Managing Available Memory + + [96]10.2 How Can We Access a Page Frame? + + [97]10.3 A Kernel Heap + + [98]10.4 Further reading + * [99]11 User Mode + + [100]11.1 Segments for User Mode + + [101]11.2 Setting Up For User Mode + + [102]11.3 Entering User Mode + + [103]11.4 Using C for User Mode Programs + o [104]11.4.1 A C Library + + [105]11.5 Further Reading + * [106]12 File Systems + + [107]12.1 Why a File System? + + [108]12.2 A Simple Read-Only File System + + [109]12.3 Inodes and Writable File Systems + + [110]12.4 A Virtual File System + + [111]12.5 Further Reading + * [112]13 System Calls + + [113]13.1 Designing System Calls + + [114]13.2 Implementing System Calls + + [115]13.3 Further Reading + * [116]14 Multitasking + + [117]14.1 Creating New Processes + + [118]14.2 Cooperative Scheduling with Yielding + + [119]14.3 Preemptive Scheduling with Interrupts + o [120]14.3.1 Programmable Interval Timer + o [121]14.3.2 Separate Kernel Stacks for Processes + o [122]14.3.3 Difficulties with Preemptive Scheduling + + [123]14.4 Further Reading + +1 Introduction + + This text is a practical guide to writing your own x86 operating + system. It is designed to give enough help with the technical details + while at the same time not reveal too much with samples and code + excerpts. We've tried to collect parts of the vast (and often + excellent) expanse of material and tutorials available, on the web and + otherwise, and add our own insights into the problems we encountered + and struggled with. + + This book is not about the theory behind operating systems, or how any + specific operating system (OS) works. For OS theory we recommend the + book Modern Operating Systems by Andrew Tanenbaum [1]. Lists and + details on current operating systems are available on the Internet. + + The starting chapters are quite detailed and explicit, to quickly get + you into coding. Later chapters give more of an outline of what is + needed, as more and more of the implementation and design becomes up to + the reader, who should now be more familiar with the world of kernel + development. At the end of some chapters there are links for further + reading, which might be interesting and give a deeper understanding of + the topics covered. + + In [124]chapter 2 and [125]3 we set up our development environment and + boot up our OS kernel in a virtual machine, eventually starting to + write code in C. We continue in [126]chapter 4 with writing to the + screen and the serial port, and then we dive into segmentation in + [127]chapter 5 and interrupts and input in [128]chapter 6. + + After this we have a quite functional but bare-bones OS kernel. In + [129]chapter 7 we start the road to user mode applications, with + virtual memory through paging ([130]chapter 8 and [131]9), memory + allocation ([132]chapter 10), and finally running a user application in + [133]chapter 11. + + In the last three chapters we discuss the more advanced topics of file + systems ([134]chapter 12), system calls ([135]chapter 13), and + multitasking ([136]chapter 14). + +1.1 About the Book + + The OS kernel and this book were produced as part of an advanced + individual course at the Royal Institute of Technology [2], Stockholm. + The authors had previously taken courses in OS theory, but had only + minor practical experience with OS kernel development. In order to get + more insight and a deeper understanding of how the theory from the + previous OS courses works out in practice, the authors decided to + create a new course, which focused on the development of a small OS. + Another goal of the course was writing a thorough tutorial on how to + develop a small OS basically from scratch, and this short book is the + result. + + The x86 architecture is, and has been for a long time, one of the most + common hardware architectures. It was not a difficult choice to use the + x86 architecture as the target of the OS, with its large community, + extensive reference material and mature emulators. The documentation + and information surrounding the details of the hardware we had to work + with was not always easy to find or understand, despite (or perhaps due + to) the age of the architecture. + + The OS was developed in about six weeks of full-time work. The + implementation was done in many small steps, and after each step the OS + was tested manually. By developing in this incremental and iterative + way, it was often easier to find any bugs that were introduced, since + only a small part of the code had changed since the last known good + state of the code. We encourage the reader to work in a similar way. + + During the six weeks of development, almost every single line of code + was written by the authors together (this way of working is also called + pair-programming). It is our belief that we managed to avoid a lot of + bugs due to this style of development, but this is hard to prove + scientifically. + +1.2 The Reader + + The reader of this book should be comfortable with UNIX/Linux, systems + programming, the C language and computer systems in general (such as + hexadecimal notation [3]). This book could be a way to get started + learning those things, but it will be more difficult, and developing an + operating system is already challenging on its own. Search engines and + other tutorials are often helpful if you get stuck. + +1.3 Credits, Thanks and Acknowledgements + + We'd like to thank the OSDev community [4] for their great wiki and + helpful members, and James Malloy for his eminent kernel development + tutorial [5]. We'd also like to thank our supervisor Torbjörn Granlund + for his insightful questions and interesting discussions. + + Most of the CSS formatting of the book is based on the work by Scott + Chacon for the book Pro Git, [137]http://progit.org/. + +1.4 Contributors + + We are very grateful for the patches that people send us. The following + users have all contributed to this book: + * [138]alexschneider + * [139]Avidanborisov + * [140]nirs + * [141]kedarmhaswade + * [142]vamanea + * [143]ansjob + +1.5 Changes and Corrections + + This book is hosted on Github - if you have any suggestions, comments + or corrections, just fork the book, write your changes, and send us a + pull request. We'll happily incorporate anything that makes this book + better. + +1.6 Issues and where to get help + + If you run into problems while reading the book, please check the + issues on Github for help: + [144]https://github.com/littleosbook/littleosbook/issues. + +1.7 License + + All content is under the Creative Commons Attribution Non Commercial + Share Alike 3.0 license, + [145]http://creativecommons.org/licenses/by-nc-sa/3.0/us/. The code + samples are in the public domain - use them however you want. + References to this book are always received with warmth. + +2 First Steps + + Developing an operating system (OS) is no easy task, and the question + "How do I even begin to solve this problem?" is likely to come up + several times during the course of the project for different problems. + This chapter will help you set up your development environment and + booting a very small (and primitive) operating system. + +2.1 Tools + +2.1.1 Quick Setup + + We (the authors) have used Ubuntu [6] as the operating system for doing + OS development, running it both physically and virtually (using the + virtual machine VirtualBox [7]). A quick way to get everything up and + running is to use the same setup as we did, since we know that these + tools work with the samples provided in this book. + + Once Ubuntu is installed, either physical or virtual, the following + packages should be installed using apt-get: + sudo apt-get install build-essential nasm genisoimage bochs bochs-sdl + +2.1.2 Programming Languages + + The operating system will be developed using the C programming language + [8][9], using GCC [10]. We use C because developing an OS requires a + very precise control of the generated code and direct access to memory. + Other languages that provide the same features can also be used, but + this book will only cover C. + + The code will make use of one type attribute that is specific for GCC: + __attribute__((packed)) + + This attribute allows us to ensure that the compiler uses a memory + layout for a struct exactly as we define it in the code. This is + explained in more detail in the next chapter. + + Due to this attribute, the example code might be hard to compile using + a C compiler other than GCC. + + For writing assembly code, we have chosen NASM [11] as the assembler, + since we prefer NASM's syntax over GNU Assembler. + + Bash [12] will be used as the scripting language throughout the book. + +2.1.3 Host Operating System + + All the code examples assumes that the code is being compiled on a UNIX + like operating system. All code examples have been successfully + compiled using Ubuntu [6] versions 11.04 and 11.10. + +2.1.4 Build System + + Make [13] has been used when constructing the Makefile examples. + +2.1.5 Virtual Machine + + When developing an OS it is very convenient to be able to run your code + in a virtual machine instead of on a physical computer, since starting + your OS in a virtual machine is much faster than getting your OS onto a + physical medium and then running it on a physical machine. Bochs [14] + is an emulator for the x86 (IA-32) platform which is well suited for OS + development due to its debugging features. Other popular choices are + QEMU [15] and VirtualBox [7]. This book uses Bochs. + + By using a virtual machine we cannot ensure that our OS works on real, + physical hardware. The environment simulated by the virtual machine is + designed to be very similar to their physical counterparts, and the OS + can be tested on one by just copying the executable to a CD and finding + a suitable machine. + +2.2 Booting + + Booting an operating system consists of transferring control along a + chain of small programs, each one more "powerful" than the previous + one, where the operating system is the last "program". See the + following figure for an example of the boot process: + An example of the boot process. Each box is a program. + + An example of the boot process. Each box is a program. + +2.2.1 BIOS + + When the PC is turned on, the computer will start a small program that + adheres to the Basic Input Output System (BIOS) [16] standard. This + program is usually stored on a read only memory chip on the motherboard + of the PC. The original role of the BIOS program was to export some + library functions for printing to the screen, reading keyboard input + etc. Modern operating systems do not use the BIOS' functions, they use + drivers that interact directly with the hardware, bypassing the BIOS. + Today, BIOS mainly runs some early diagnostics (power-on-self-test) and + then transfers control to the bootloader. + +2.2.2 The Bootloader + + The BIOS program will transfer control of the PC to a program called a + bootloader. The bootloader's task is to transfer control to us, the + operating system developers, and our code. However, due to some + restrictions[146]^1 of the hardware and because of backward + compatibility, the bootloader is often split into two parts: the first + part of the bootloader will transfer control to the second part, which + finally gives control of the PC to the operating system. + + Writing a bootloader involves writing a lot of low-level code that + interacts with the BIOS. Therefore, an existing bootloader will be + used: the GNU GRand Unified Bootloader (GRUB) [17]. + + Using GRUB, the operating system can be built as an ordinary ELF [18] + executable, which will be loaded by GRUB into the correct memory + location. The compilation of the kernel requires that the code is laid + out in memory in a specific way (how to compile the kernel will be + discussed later in this chapter). + +2.2.3 The Operating System + + GRUB will transfer control to the operating system by jumping to a + position in memory. Before the jump, GRUB will look for a magic number + to ensure that it is actually jumping to an OS and not some random + code. This magic number is part of the multiboot specification [19] + which GRUB adheres to. Once GRUB has made the jump, the OS has full + control of the computer. + +2.3 Hello Cafebabe + + This section will describe how to implement of the smallest possible OS + that can be used together with GRUB. The only thing the OS will do is + write 0xCAFEBABE to the eax register (most people would probably not + even call this an OS). + +2.3.1 Compiling the Operating System + + This part of the OS has to be written in assembly code, since C + requires a stack, which isn't available (the chapter [147]"Getting to + C" describes how to set one up). Save the following code in a file + called loader.s: + global loader ; the entry symbol for ELF + + MAGIC_NUMBER equ 0x1BADB002 ; define the magic number constant + FLAGS equ 0x0 ; multiboot flags + CHECKSUM equ -MAGIC_NUMBER ; calculate the checksum + ; (magic number + checksum + flags should eq +ual 0) + + section .text: ; start of the text (code) section + align 4 ; the code must be 4 byte aligned + dd MAGIC_NUMBER ; write the magic number to the machine code +, + dd FLAGS ; the flags, + dd CHECKSUM ; and the checksum + + loader: ; the loader label (defined as entry point i +n linker script) + mov eax, 0xCAFEBABE ; place the number 0xCAFEBABE in the registe +r eax + .loop: + jmp .loop ; loop forever + + The only thing this OS will do is write the very specific number + 0xCAFEBABE to the eax register. It is very unlikely that the number + 0xCAFEBABE would be in the eax register if the OS did not put it there. + + The file loader.s can be compiled into a 32 bits ELF [18] object file + with the following command: + nasm -f elf32 loader.s + +2.3.2 Linking the Kernel + + The code must now be linked to produce an executable file, which + requires some extra thought compared to when linking most programs. We + want GRUB to load the kernel at a memory address larger than or equal + to 0x00100000 (1 megabyte (MB)), because addresses lower than 1 MB are + used by GRUB itself, BIOS and memory-mapped I/O. Therefore, the + following linker script is needed (written for GNU LD [20]): +ENTRY(loader) /* the name of the entry label */ + +SECTIONS { + . = 0x00100000; /* the code should be loaded at 1 MB */ + + .text ALIGN (0x1000) : /* align at 4 KB */ + { + *(.text) /* all text sections from all files */ + } + + .rodata ALIGN (0x1000) : /* align at 4 KB */ + { + *(.rodata*) /* all read-only data sections from all files */ + } + + .data ALIGN (0x1000) : /* align at 4 KB */ + { + *(.data) /* all data sections from all files */ + } + + .bss ALIGN (0x1000) : /* align at 4 KB */ + { + *(COMMON) /* all COMMON sections from all files */ + *(.bss) /* all bss sections from all files */ + } +} + + Save the linker script into a file called link.ld. The executable can + now be linked with the following command: + ld -T link.ld -melf_i386 loader.o -o kernel.elf + + The final executable will be called kernel.elf. + +2.3.3 Obtaining GRUB + + The GRUB version we will use is GRUB Legacy, since the OS ISO image can + then be generated on systems using both GRUB Legacy and GRUB 2. More + specifically, the GRUB Legacy stage2_eltorito bootloader will be used. + This file can be built from GRUB 0.97 by downloading the source from + [148]ftp://alpha.gnu.org/gnu/grub/grub-0.97.tar.gz. However, the + configure script doesn't work well with Ubuntu [21], so the binary file + can be downloaded from + [149]http://littleosbook.github.com/files/stage2_eltorito. Copy the + file stage2_eltorito to the folder that already contains loader.s and + link.ld. + +2.3.4 Building an ISO Image + + The executable must be placed on a media that can be loaded by a + virtual or physical machine. In this book we will use ISO [22] image + files as the media, but one can also use floppy images, depending on + what the virtual or physical machine supports. + + We will create the kernel ISO image with the program genisoimage. A + folder must first be created that contains the files that will be on + the ISO image. The following commands create the folder and copy the + files to their correct places: + mkdir -p iso/boot/grub # create the folder structure + cp stage2_eltorito iso/boot/grub/ # copy the bootloader + cp kernel.elf iso/boot/ # copy the kernel + + A configuration file menu.lst for GRUB must be created. This file tells + GRUB where the kernel is located and configures some options: + default=0 + timeout=0 + + title os + kernel /boot/kernel.elf + + Place the file menu.lst in the folder iso/boot/grub/. The contents of + the iso folder should now look like the following figure: + iso + |-- boot + |-- grub + | |-- menu.lst + | |-- stage2_eltorito + |-- kernel.elf + + The ISO image can then be generated with the following command: + genisoimage -R \ + -b boot/grub/stage2_eltorito \ + -no-emul-boot \ + -boot-load-size 4 \ + -A os \ + -input-charset utf8 \ + -quiet \ + -boot-info-table \ + -o os.iso \ + iso + + For more information about the flags used in the command, see the + manual for genisoimage. + + The ISO image os.iso now contains the kernel executable, the GRUB + bootloader and the configuration file. + +2.3.5 Running Bochs + + Now we can run the OS in the Bochs emulator using the os.iso ISO image. + Bochs needs a configuration file to start and an example of a simple + configuration file is given below: + megs: 32 + display_library: sdl + romimage: file=/usr/share/bochs/BIOS-bochs-latest + vgaromimage: file=/usr/share/bochs/VGABIOS-lgpl-latest + ata0-master: type=cdrom, path=os.iso, status=inserted + boot: cdrom + log: bochslog.txt + clock: sync=realtime, time0=local + cpu: count=1, ips=1000000 + + You might need to change the path to romimage and vgaromimage depending + on how you installed Bochs. More information about the Bochs config + file can be found at Boch's website [23]. + + If you saved the configuration in a file named bochsrc.txt then you can + run Bochs with the following command: + bochs -f bochsrc.txt -q + + The flag -f tells Bochs to use the given configuration file and the + flag -q tells Bochs to skip the interactive start menu. You should now + see Bochs starting and displaying a console with some information from + GRUB on it. + + After quitting Bochs, display the log produced by Boch: + cat bochslog.txt + + You should now see the contents of the registers of the CPU simulated + by Bochs somewhere in the output. If you find RAX=00000000CAFEBABE or + EAX=CAFEBABE (depending on if you are running Bochs with or without 64 + bit support) in the output then your OS has successfully booted! + +2.4 Further Reading + + * Gustavo Duertes has written an in-depth article about what actually + happens when a x86 computer boots up, + [150]http://duartes.org/gustavo/blog/post/how-computers-boot-up + * Gustavo continues to describe what the kernel does in the very + early stages at + [151]http://duartes.org/gustavo/blog/post/kernel-boot-process + * The OSDev wiki also contains a nice article about booting an x86 + computer: [152]http://wiki.osdev.org/Boot_Sequence + +3 Getting to C + + This chapter will show you how to use C instead of assembly code as the + programming language for the OS. Assembly is very good for interacting + with the CPU and enables maximum control over every aspect of the code. + However, at least for the authors, C is a much more convenient language + to use. Therefore, we would like to use C as much as possible and use + assembly code only where it make sense. + +3.1 Setting Up a Stack + + One prerequisite for using C is a stack, since all non-trivial C + programs use a stack. Setting up a stack is not harder than to make the + esp register point to the end of an area of free memory (remember that + the stack grows towards lower addresses on the x86) that is correctly + aligned (alignment on 4 bytes is recommended from a performance + perspective). + + We could point esp to a random area in memory since, so far, the only + thing in the memory is GRUB, BIOS, the OS kernel and some memory-mapped + I/O. This is not a good idea - we don't know how much memory is + available or if the area esp would point to is used by something else. + A better idea is to reserve a piece of uninitialized memory in the bss + section in the ELF file of the kernel. It is better to use the bss + section instead of the data section to reduce the size of the OS + executable. Since GRUB understands ELF, GRUB will allocate any memory + reserved in the bss section when loading the OS. + + The NASM pseudo-instruction resb [24] can be used to declare + uninitialized data: + KERNEL_STACK_SIZE equ 4096 ; size of stack in bytes + + section .bss + align 4 ; align at 4 bytes + kernel_stack: ; label points to beginning of m +emory + resb KERNEL_STACK_SIZE ; reserve stack for the kernel + + There is no need to worry about the use of uninitialized memory for the + stack, since it is not possible to read a stack location that has not + been written (without manual pointer fiddling). A (correct) program can + not pop an element from the stack without having pushed an element onto + the stack first. Therefore, the memory locations of the stack will + always be written to before they are being read. + + The stack pointer is then set up by pointing esp to the end of the + kernel_stack memory: + mov esp, kernel_stack + KERNEL_STACK_SIZE ; point esp to the start of the + ; stack (end of memory area) + +3.2 Calling C Code From Assembly + + The next step is to call a C function from assembly code. There are + many different conventions for how to call C code from assembly code + [25]. This book uses the cdecl calling convention, since that is the + one used by GCC. The cdecl calling convention states that arguments to + a function should be passed via the stack (on x86). The arguments of + the function should be pushed on the stack in a right-to-left order, + that is, you push the rightmost argument first. The return value of the + function is placed in the eax register. The following code shows an + example: + /* The C function */ + int sum_of_three(int arg1, int arg2, int arg3) + { + return arg1 + arg2 + arg3; + } + ; The assembly code + external sum_of_three ; the function sum_of_three is defined elsewhere + + push dword 3 ; arg3 + push dword 2 ; arg2 + push dword 1 ; arg1 + call sum_of_three ; call the function, the result will be in eax + +3.2.1 Packing Structs + + In the rest of this book, you will often come across "configuration + bytes" that are a collection of bits in a very specific order. Below + follows an example with 32 bits: +Bit: | 31 24 | 23 8 | 7 0 | +Content: | index | address | config | + + Instead of using an unsigned integer, unsigned int, for handling such + configurations, it is much more convenient to use "packed structures": + struct example { + unsigned char config; /* bit 0 - 7 */ + unsigned short address; /* bit 8 - 23 */ + unsigned char index; /* bit 24 - 31 */ + }; + + When using the struct in the previous example there is no guarantee + that the size of the struct will be exactly 32 bits - the compiler can + add some padding between elements for various reasons, for example to + speed up element access or due to requirements set by the hardware + and/or compiler. When using a struct to represent configuration bytes, + it is very important that the compiler does not add any padding, + because the struct will eventually be treated as a 32 bit unsigned + integer by the hardware. The attribute packed can be used to force GCC + to not add any padding: + struct example { + unsigned char config; /* bit 0 - 7 */ + unsigned short address; /* bit 8 - 23 */ + unsigned char index; /* bit 24 - 31 */ + } __attribute__((packed)); + + Note that __attribute__((packed)) is not part of the C standard - it + might not work with all C compilers. + +3.3 Compiling C Code + + When compiling the C code for the OS, a lot of flags to GCC need to be + used. This is because the C code should not assume the presence of a + standard library, since there is no standard library available for our + OS. For more information about the flags, see the GCC manual. + + The flags used for compiling the C code are: + -m32 -nostdlib -nostdinc -fno-builtin -fno-stack-protector -nostartfiles + -nodefaultlibs + + As always when writing C programs we recommend turning on all warnings + and treat warnings as errors: + -Wall -Wextra -Werror + + You can now create a function kmain in a file called kmain.c that you + call from loader.s. At this point, kmain probably won't need any + arguments (but in later chapters it will). + +3.4 Build Tools + + Now is also probably a good time to set up some build tools to make it + easier to compile and test-run the OS. We recommend using make [13], + but there are plenty of other build systems available. A simple + Makefile for the OS could look like the following example: + OBJECTS = loader.o kmain.o + CC = gcc + CFLAGS = -m32 -nostdlib -nostdinc -fno-builtin -fno-stack-protector \ + -nostartfiles -nodefaultlibs -Wall -Wextra -Werror -c + LDFLAGS = -T link.ld -melf_i386 + AS = nasm + ASFLAGS = -f elf + + all: kernel.elf + + kernel.elf: $(OBJECTS) + ld $(LDFLAGS) $(OBJECTS) -o kernel.elf + + os.iso: kernel.elf + cp kernel.elf iso/boot/kernel.elf + genisoimage -R \ + -b boot/grub/stage2_eltorito \ + -no-emul-boot \ + -boot-load-size 4 \ + -A os \ + -input-charset utf8 \ + -quiet \ + -boot-info-table \ + -o os.iso \ + iso + + run: os.iso + bochs -f bochsrc.txt -q + + %.o: %.c + $(CC) $(CFLAGS) $< -o $@ + + %.o: %.s + $(AS) $(ASFLAGS) $< -o $@ + + clean: + rm -rf *.o kernel.elf os.iso + + The contents of your working directory should now look like the + following figure: + . + |-- bochsrc.txt + |-- iso + | |-- boot + | |-- grub + | |-- menu.lst + | |-- stage2_eltorito + |-- kmain.c + |-- loader.s + |-- Makefile + + You should now be able to start the OS with the simple command make + run, which will compile the kernel and boot it up in Bochs (as defined + in the Makefile above). + +3.5 Further Reading + + * Kernigan & Richie's book, The C Programming Language, Second + Edition, [8] is great for learning about all the aspects of C. + +4 Output + + This chapter will present how to display text on the console as well as + writing data to the serial port. Furthermore, we will create our first + driver, that is, code that acts as a layer between the kernel and the + hardware, providing a higher abstraction than communicating directly + with the hardware. The first part of this chapter is about creating a + driver for the framebuffer [26] to be able to display text on the + console. The second part shows how to create a driver for the serial + port. Bochs can store output from the serial port in a file, + effectively creating a logging mechanism for the operating system. + +4.1 Interacting with the Hardware + + There are usually two different ways to interact with the hardware, + memory-mapped I/O and I/O ports. + + If the hardware uses memory-mapped I/O then you can write to a specific + memory address and the hardware will be updated with the new data. One + example of this is the framebuffer, which will be discussed in more + detail later. For example, if you write the value 0x410F to address + 0x000B8000, you will see the letter A in white color on a black + background (see the section on [153]the framebuffer for more details). + + If the hardware uses I/O ports then the assembly code instructions out + and in must be used to communicate with the hardware. The instruction + out takes two parameters: the address of the I/O port and the data to + send. The instruction in takes a single parameter, the address of the + I/O port, and returns data from the hardware. One can think of I/O + ports as communicating with hardware the same way as you communicate + with a server using sockets. The cursor (the blinking rectangle) of the + framebuffer is one example of hardware controlled via I/O ports on a + PC. + +4.2 The Framebuffer + + The framebuffer is a hardware device that is capable of displaying a + buffer of memory on the screen [26]. The framebuffer has 80 columns and + 25 rows, and the row and column indices start at 0 (so rows are + labelled 0 - 24). + +4.2.1 Writing Text + + Writing text to the console via the framebuffer is done with + memory-mapped I/O. The starting address of the memory-mapped I/O for + the framebuffer is 0x000B8000 [27]. The memory is divided into 16 bit + cells, where the 16 bits determine both the character, the foreground + color and the background color. The highest eight bits is the ASCII + [28] value of the character, bit 7 - 4 the background and bit 3 - 0 the + foreground, as can be seen in the following figure: +Bit: | 15 14 13 12 11 10 9 8 | 7 6 5 4 | 3 2 1 0 | +Content: | ASCII | FG | BG | + + The available colors are shown in the following table: + Color Value Color Value Color Value Color Value + Black 0 Red 4 Dark grey 8 Light red 12 + Blue 1 Magenta 5 Light blue 9 Light magenta 13 + Green 2 Brown 6 Light green 10 Light brown 14 + Cyan 3 Light grey 7 Light cyan 11 White 15 + + The first cell corresponds to row zero, column zero on the console. + Using an ASCII table, one can see that A corresponds to 65 or 0x41. + Therefore, to write the character A with a green foreground (2) and + dark grey background (8) at place (0,0), the following assembly code + instruction is used: + mov [0x000B8000], 0x4128 + + The second cell then corresponds to row zero, column one and its + address is therefore: + 0x000B8000 + 16 = 0x000B8010 + + Writing to the framebuffer can also be done in C by treating the + address 0x000B8000 as a char pointer, char *fb = (char *) 0x000B8000. + Then, writing A at place (0,0) with green foreground and dark grey + background becomes: + fb[0] = 'A'; + fb[1] = 0x28; + + The following code shows how this can be wrapped into a function: + /** fb_write_cell: + * Writes a character with the given foreground and background to position +i + * in the framebuffer. + * + * @param i The location in the framebuffer + * @param c The character + * @param fg The foreground color + * @param bg The background color + */ + void fb_write_cell(unsigned int i, char c, unsigned char fg, unsigned char b +g) + { + fb[i] = c; + fb[i + 1] = ((fg & 0x0F) << 4) | (bg & 0x0F) + } + + The function can then be used as follows: + #define FB_GREEN 2 + #define FB_DARK_GREY 8 + + fb_write_cell(0, 'A', FB_GREEN, FB_DARK_GREY); + +4.2.2 Moving the Cursor + + Moving the cursor of the framebuffer is done via two different I/O + ports. The cursor's position is determined with a 16 bits integer: 0 + means row zero, column zero; 1 means row zero, column one; 80 means row + one, column zero and so on. Since the position is 16 bits large, and + the out assembly code instruction argument is 8 bits, the position must + be sent in two turns, first 8 bits then the next 8 bits. The + framebuffer has two I/O ports, one for accepting the data, and one for + describing the data being received. Port 0x3D4 [29] is the port that + describes the data and port 0x3D5 [29] is for the data itself. + + To set the cursor at row one, column zero (position 80 = 0x0050), one + would use the following assembly code instructions: + out 0x3D4, 14 ; 14 tells the framebuffer to expect the highest 8 bits o +f the position + out 0x3D5, 0x00 ; sending the highest 8 bits of 0x0050 + out 0x3D4, 15 ; 15 tells the framebuffer to expect the lowest 8 bits of + the position + out 0x3D5, 0x50 ; sending the lowest 8 bits of 0x0050 + + The out assembly code instruction can't be executed directly in C. + Therefore it is a good idea to wrap out in a function in assembly code + which can be accessed from C via the cdecl calling standard [25]: + global outb ; make the label outb visible outside this file + + ; outb - send a byte to an I/O port + ; stack: [esp + 8] the data byte + ; [esp + 4] the I/O port + ; [esp ] return address + outb: + mov al, [esp + 8] ; move the data to be sent into the al register + mov dx, [esp + 4] ; move the address of the I/O port into the dx regi +ster + out dx, al ; send the data to the I/O port + ret ; return to the calling function + + By storing this function in a file called io.s and also creating a + header io.h, the out assembly code instruction can be conveniently + accessed from C: + #ifndef INCLUDE_IO_H + #define INCLUDE_IO_H + + /** outb: + * Sends the given data to the given I/O port. Defined in io.s + * + * @param port The I/O port to send the data to + * @param data The data to send to the I/O port + */ + void outb(unsigned short port, unsigned char data); + + #endif /* INCLUDE_IO_H */ + + Moving the cursor can now be wrapped in a C function: + #include "io.h" + + /* The I/O ports */ + #define FB_COMMAND_PORT 0x3D4 + #define FB_DATA_PORT 0x3D5 + + /* The I/O port commands */ + #define FB_HIGH_BYTE_COMMAND 14 + #define FB_LOW_BYTE_COMMAND 15 + + /** fb_move_cursor: + * Moves the cursor of the framebuffer to the given position + * + * @param pos The new position of the cursor + */ + void fb_move_cursor(unsigned short pos) + { + outb(FB_COMMAND_PORT, FB_HIGH_BYTE_COMMAND); + outb(FB_DATA_PORT, ((pos >> 8) & 0x00FF)); + outb(FB_COMMAND_PORT, FB_LOW_BYTE_COMMAND); + outb(FB_DATA_PORT, pos & 0x00FF); + } + +4.2.3 The Driver + + The driver should provide an interface that the rest of the code in the + OS will use for interacting with the framebuffer. There is no right or + wrong in what functionality the interface should provide, but a + suggestion is to have a write function with the following declaration: + int write(char *buf, unsigned int len); + + The write function writes the contents of the buffer buf of length len + to the screen. The write function should automatically advance the + cursor after a character has been written and scroll the screen if + necessary. + +4.3 The Serial Ports + + The serial port [30] is an interface for communicating between hardware + devices and although it is available on almost all motherboards, it is + seldom exposed to the user in the form of a DE-9 connector nowadays. + The serial port is easy to use, and, more importantly, it can be used + as a logging utility in Bochs. If a computer has support for a serial + port, then it usually has support for multiple serial ports, but we + will only make use of one of the ports. This is because we will only + use the serial ports for logging. Furthermore, we will only use the + serial ports for output, not input. The serial ports are completely + controlled via I/O ports. + +4.3.1 Configuring the Serial Port + + The first data that need to be sent to the serial port is configuration + data. In order for two hardware devices to be able to talk to each + other they must agree upon a couple of things. These things include: + * The speed used for sending data (bit or baud rate) + * If any error checking should be used for the data (parity bit, stop + bits) + * The number of bits that represent a unit of data (data bits) + +4.3.2 Configuring the Line + + Configuring the line means to configure how data is being sent over the + line. The serial port has an I/O port, the line command port, that is + used for configuration. + + First the speed for sending data will be set. The serial port has an + internal clock that runs at 115200 Hz. Setting the speed means sending + a divisor to the serial port, for example sending 2 results in a speed + of 115200 / 2 = 57600 Hz. + + The divisor is a 16 bit number but we can only send 8 bits at a time. + We must therefore send an instruction telling the serial port to first + expect the highest 8 bits, then the lowest 8 bits. This is done by + sending 0x80 to the line command port. An example is shown below: + #include "io.h" /* io.h is implement in the section "Moving the cursor" */ + + /* The I/O ports */ + + /* All the I/O ports are calculated relative to the data port. This is becau +se + * all serial ports (COM1, COM2, COM3, COM4) have their ports in the same + * order, but they start at different values. + */ + + #define SERIAL_COM1_BASE 0x3F8 /* COM1 base port */ + + #define SERIAL_DATA_PORT(base) (base) + #define SERIAL_FIFO_COMMAND_PORT(base) (base + 2) + #define SERIAL_LINE_COMMAND_PORT(base) (base + 3) + #define SERIAL_MODEM_COMMAND_PORT(base) (base + 4) + #define SERIAL_LINE_STATUS_PORT(base) (base + 5) + + /* The I/O port commands */ + + /* SERIAL_LINE_ENABLE_DLAB: + * Tells the serial port to expect first the highest 8 bits on the data port +, + * then the lowest 8 bits will follow + */ + #define SERIAL_LINE_ENABLE_DLAB 0x80 + + /** serial_configure_baud_rate: + * Sets the speed of the data being sent. The default speed of a serial + * port is 115200 bits/s. The argument is a divisor of that number, hence + * the resulting speed becomes (115200 / divisor) bits/s. + * + * @param com The COM port to configure + * @param divisor The divisor + */ + void serial_configure_baud_rate(unsigned short com, unsigned short divisor) + { + outb(SERIAL_LINE_COMMAND_PORT(com), + SERIAL_LINE_ENABLE_DLAB); + outb(SERIAL_DATA_PORT(com), + (divisor >> 8) & 0x00FF); + outb(SERIAL_DATA_PORT(com), + divisor & 0x00FF); + } + + The way that data should be sent must be configured. This is also done + via the line command port by sending a byte. The layout of the 8 bits + looks like the following: +Bit: | 7 | 6 | 5 4 3 | 2 | 1 0 | +Content: | d | b | prty | s | dl | + + A description for each name can be found in the table below (and in + [31]): + Name Description + d Enables (d = 1) or disables (d = 0) DLAB + b If break control is enabled (b = 1) or disabled (b = 0) + prty The number of parity bits to use + s The number of stop bits to use (s = 0 equals 1, s = 1 equals 1.5 or + 2) + dl Describes the length of the data + + We will use the mostly standard value 0x03 [31], meaning a length of 8 + bits, no parity bit, one stop bit and break control disabled. This is + sent to the line command port, as seen in the following example: + /** serial_configure_line: + * Configures the line of the given serial port. The port is set to have a + * data length of 8 bits, no parity bits, one stop bit and break control + * disabled. + * + * @param com The serial port to configure + */ + void serial_configure_line(unsigned short com) + { + /* Bit: | 7 | 6 | 5 4 3 | 2 | 1 0 | + * Content: | d | b | prty | s | dl | + * Value: | 0 | 0 | 0 0 0 | 0 | 1 1 | = 0x03 + */ + outb(SERIAL_LINE_COMMAND_PORT(com), 0x03); + } + + The article on OSDev [31] has a more in-depth explanation of the + values. + +4.3.3 Configuring the Buffers + + When data is transmitted via the serial port it is placed in buffers, + both when receiving and sending data. This way, if you send data to the + serial port faster than it can send it over the wire, it will be + buffered. However, if you send too much data too fast the buffer will + be full and data will be lost. In other words, the buffers are FIFO + queues. The FIFO queue configuration byte looks like the following + figure: +Bit: | 7 6 | 5 | 4 | 3 | 2 | 1 | 0 | +Content: | lvl | bs | r | dma | clt | clr | e | + + A description for each name can be found in the table below: + Name Description + lvl How many bytes should be stored in the FIFO buffers + bs If the buffers should be 16 or 64 bytes large + r Reserved for future use + dma How the serial port data should be accessed + clt Clear the transmission FIFO buffer + clr Clear the receiver FIFO buffer + e If the FIFO buffer should be enabled or not + + We use the value 0xC7 = 11000111 that: + * Enables FIFO + * Clear both receiver and transmission FIFO queues + * Use 14 bytes as size of queue + + The WikiBook on serial programming [32] explains the values in more + depth. + +4.3.4 Configuring the Modem + + The modem control register is used for very simple hardware flow + control via the Ready To Transmit (RTS) and Data Terminal Ready (DTR) + pins. When configuring the serial port we want RTS and DTR to be 1, + which means that we are ready to send data. + + The modem configuration byte is shown in the following figure: +Bit: | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | +Content: | r | r | af | lb | ao2 | ao1 | rts | dtr | + + A description for each name can be found in the table below: + Name Description + r Reserved + af Autoflow control enabled + lb Loopback mode (used for debugging serial ports) + ao2 Auxiliary output 2, used for receiving interrupts + ao1 Auxiliary output 1 + rts Ready To Transmit + dtr Data Terminal Ready + + We don't need to enable interrupts, because we won't handle any + received data. Therefore we use the configuration value 0x03 = 00000011 + (RTS = 1 and DTS = 1). + +4.3.5 Writing Data to the Serial Port + + Writing data to the serial port is done via the data I/O port. However, + before writing, the transmit FIFO queue has to be empty (all previous + writes must have finished). The transmit FIFO queue is empty if bit 5 + of the line status I/O port is equal to one. + + Reading the contents of an I/O port is done via the in assembly code + instruction. There is no way to use the in assembly code instruction + from C, therefore it has to be wrapped (the same way as the out + assembly code instruction): + global inb + + ; inb - returns a byte from the given I/O port + ; stack: [esp + 4] The address of the I/O port + ; [esp ] The return address + inb: + mov dx, [esp + 4] ; move the address of the I/O port to the dx reg +ister + in al, dx ; read a byte from the I/O port and store it in +the al register + ret ; return the read byte + /* in file io.h */ + + /** inb: + * Read a byte from an I/O port. + * + * @param port The address of the I/O port + * @return The read byte + */ + unsigned char inb(unsigned short port); + + Checking if the transmit FIFO is empty can then be done from C: + #include "io.h" + + /** serial_is_transmit_fifo_empty: + * Checks whether the transmit FIFO queue is empty or not for the given COM + * port. + * + * @param com The COM port + * @return 0 if the transmit FIFO queue is not empty + * 1 if the transmit FIFO queue is empty + */ + int serial_is_transmit_fifo_empty(unsigned int com) + { + /* 0x20 = 0010 0000 */ + return inb(SERIAL_LINE_STATUS_PORT(com)) & 0x20; + } + + Writing to a serial port means spinning as long as the transmit FIFO + queue isn't empty, and then writing the data to the data I/O port. + +4.3.6 Configuring Bochs + + To save the output from the first serial serial port the Bochs + configuration file bochsrc.txt must be updated. The com1 configuration + instructs Bochs how to handle first serial port: + com1: enabled=1, mode=file, dev=com1.out + + The output from serial port one will now be stored in the file + com1.out. + +4.3.7 The Driver + + We recommend that you implement a write function for the serial port + similar to the write function in the driver for the framebuffer. To + avoid name clashes with the write function for the framebuffer it is a + good idea to name the functions fb_write and serial_write to + distinguish them. + + We further recommend that you try to write a printf-like function, see + section 7.3 in [8]. The printf function could take an additional + argument to decide to which device to write the output (framebuffer or + serial). + + A final recommendation is that you create some way of distinguishing + the severeness of the log messages, for example by prepending the + messages with DEBUG, INFO or ERROR. + +4.4 Further Reading + + * The book "Serial programming" (available on WikiBooks) has a great + section on programming the serial port, + [154]http://en.wikibooks.org/wiki/Serial_Programming/8250_UART_Prog + ramming#UART_Registers + * The OSDev wiki has a page with a lot of information about the + serial ports, [155]http://wiki.osdev.org/Serial_ports + +5 Segmentation + + Segmentation in x86 means accessing the memory through segments. + Segments are portions of the address space, possibly overlapping, + specified by a base address and a limit. To address a byte in segmented + memory you use a 48-bit logical address: 16 bits that specifies the + segment and 32-bits that specifies what offset within that segment you + want. The offset is added to the base address of the segment, and the + resulting linear address is checked against the segment's limit - see + the figure below. If everything works out fine (including access-rights + checks ignored for now) the result is a linear address. When paging is + disabled, then the linear address space is mapped 1:1 onto the physical + address space, and the physical memory can be accessed. (See the + chapter [156]"Paging" for how to enable paging.) + Translation of logical addresses to linear addresses. + + Translation of logical addresses to linear addresses. + + To enable segmentation you need to set up a table that describes each + segment - a segment descriptor table. In x86, there are two types of + descriptor tables: the Global Descriptor Table (GDT) and Local + Descriptor Tables (LDT). An LDT is set up and managed by user-space + processes, and all processes have their own LDT. LDTs can be used if a + more complex segmentation model is desired - we won't use it. The GDT + is shared by everyone - it's global. + + As we discuss in the sections on virtual memory and paging, + segmentation is rarely used more than in a minimal setup, similar to + what we do below. + +5.1 Accessing Memory + + Most of the time when accessing memory there is no need to explicitly + specify the segment to use. The processor has six 16-bit segment + registers: cs, ss, ds, es, gs and fs. The register cs is the code + segment register and specifies the segment to use when fetching + instructions. The register ss is used whenever accessing the stack + (through the stack pointer esp), and ds is used for other data + accesses. The OS is free to use the registers es, gs and fs however it + want. + + Below is an example showing implicit use of the segment registers: + func: + mov eax, [esp+4] + mov ebx, [eax] + add ebx, 8 + mov [eax], ebx + ret + + The above example can be compared with the following one that makes + explicit use of the segment registers: + func: + mov eax, [ss:esp+4] + mov ebx, [ds:eax] + add ebx, 8 + mov [ds:eax], ebx + ret + + You don't need to use ss for storing the stack segment selector, or ds + for the data segment selector. You could store the stack segment + selector in ds and vice versa. However, in order to use the implicit + style shown above, you must store the segment selectors in their + indented registers. + + Segment descriptors and their fields are described in figure 3-8 in the + Intel manual [33]. + +5.2 The Global Descriptor Table (GDT) + + A GDT/LDT is an array of 8-byte segment descriptors. The first + descriptor in the GDT is always a null descriptor and can never be used + to access memory. At least two segment descriptors (plus the null + descriptor) are needed for the GDT, because the descriptor contains + more information than just the base and limit fields. The two most + relevant fields for us are the Type field and the Descriptor Privilege + Level (DPL) field. + + Table 3-1 in chapter 3 of the Intel manual [33] specifies the values + for the Type field. The table shows that the Type field can't be both + writable and executable at the same time. Therefore, two segments are + needed: one segment for executing code to put in cs (Type is + Execute-only or Execute-Read) and one segment for reading and writing + data (Type is Read/Write) to put in the other segment registers. + + The DPL specifies the privilege levels required to use the segment. x86 + allows for four privilege levels (PL), 0 to 3, where PL0 is the most + privileged. In most operating systems (eg. Linux and Windows), only PL0 + and PL3 are used. However, some operating system, such as MINIX, make + use of all levels. The kernel should be able to do anything, therefore + it uses segments with DPL set to 0 (also called kernel mode). The + current privilege level (CPL) is determined by the segment selector in + cs. + + The segments needed are described in the table below. + + CAPTION: The segment descriptors needed. + + Index Offset Name Address range Type DPL + 0 0x00 null descriptor + 1 0x08 kernel code segment 0x00000000 - 0xFFFFFFFF RX PL0 + 2 0x10 kernel data segment 0x00000000 - 0xFFFFFFFF RW PL0 + + Note that the segments overlap - they both encompass the entire linear + address space. In our minimal setup we'll only use segmentation to get + privilege levels. See the Intel manual [33], chapter 3, for details on + the other descriptor fields. + +5.3 Loading the GDT + + Loading the GDT into the processor is done with the lgdt assembly code + instruction, which takes the address of a struct that specifies the + start and size of the GDT. It is easiest to encode this information + using a [157]"packed struct" as shown in the following example: + struct gdt { + unsigned int address; + unsigned short size; + } __attribute__((packed)); + + If the content of the eax register is the address to such a struct, + then the GDT can be loaded with the assembly code shown below: + lgdt [eax] + + It might be easier if you make this instruction available from C, the + same way as was done with the assembly code instructions in and out. + + After the GDT has been loaded the segment registers needs to be loaded + with their corresponding segment selectors. The content of a segment + selector is described in the figure and table below: +Bit: | 15 3 | 2 | 1 0 | +Content: | offset (index) | ti | rpl | + + CAPTION: The layout of segment selectors. + + Name Description + rpl Requested Privilege Level - we want to execute in PL0 for now. + ti Table Indicator. 0 means that this specifies a GDT segment, 1 means + an LDT Segment. + offset (index) Offset within descriptor table. + + The offset of the segment selector is added to the start of the GDT to + get the address of the segment descriptor: 0x08 for the first + descriptor and 0x10 for the second, since each descriptor is 8 bytes. + The Requested Privilege Level (RPL) should be 0 since the kernel of the + OS should execute in privilege level 0. + + Loading the segment selector registers is easy for the data registers - + just copy the correct offsets to the registers: + mov ds, 0x10 + mov ss, 0x10 + mov es, 0x10 + . + . + . + + To load cs we have to do a "far jump": + ; code here uses the previous cs + jmp 0x08:flush_cs ; specify cs when jumping to flush_cs + + flush_cs: + ; now we've changed cs to 0x08 + + A far jump is a jump where we explicitly specify the full 48-bit + logical address: the segment selector to use and the absolute address + to jump to. It will first set cs to 0x08 and then jump to flush_cs + using its absolute address. + +5.4 Further Reading + + * Chapter 3 of the Intel manual [33] is filled with low-level and + technical details about segmentation. + * The OSDev wiki has a page about segmentation: + [158]http://wiki.osdev.org/Segmentation + * The Wikipedia page on x86 segmentation might be worth looking into: + [159]http://en.wikipedia.org/wiki/X86_memory_segmentation + +6 Interrupts and Input + + Now that the OS can produce output it would be nice if it also could + get some input. (The operating system must be able to handle interrupts + in order to read information from the keyboard). An interrupt occurs + when a hardware device, such as the keyboard, the serial port or the + timer, signals the CPU that the state of the device has changed. The + CPU itself can also send interrupts due to program errors, for example + when a program references memory it doesn't have access to, or when a + program divides a number by zero. Finally, there are also software + intterupts, which are interrupts that are caused by the int assembly + code instruction, and they are often used for system calls. + +6.1 Interrupts Handlers + + Interrupts are handled via the Interrupt Descriptor Table (IDT). The + IDT describes a handler for each interrupt. The interrupts are numbered + (0 - 255) and the handler for interrupt i is defined at the ith + position in the table. There are three different kinds of handlers for + interrupts: + * Task handler + * Interrupt handler + * Trap handler + + The task handlers use functionality specific to the Intel version of + x86, so they won't be covered here (see the Intel manual [33], chapter + 6, for more info). The only difference between an interrupt handler and + a trap handler is that the interrupt handler disables interrupts, which + means you cannot get an interrupt while at the same time handling an + interrupt. In this book, we will use trap handlers and disable + interrupts manually when we need to. + +6.2 Creating an Entry in the IDT + + An entry in the IDT for an interrupt handler consists of 64 bits. The + highest 32 bits are shown in the figure below: +Bit: | 31 16 | 15 | 14 13 | 12 | 11 | 10 9 8 | 7 6 5 | 4 3 2 1 +0 | +Content: | offset high | P | DPL | 0 | D | 1 1 0 | 0 0 0 | reserved + | + + The lowest 32 bits are presented in the following figure: +Bit: | 31 16 | 15 0 | +Content: | segment selector | offset low | + + A description for each name can be found in the table below: + Name Description + offset high The 16 highest bits of the 32 bit address in the segment. + offset low The 16 lowest bits of the 32 bits address in the segment. + p If the handler is present in memory or not (1 = present, 0 = not + present). + DPL Descriptor Privilige Level, the privilege level the handler can be + called from (0, 1, 2, 3). + D Size of gate, (1 = 32 bits, 0 = 16 bits). + segment selector The offset in the GDT. + r Reserved. + + The offset is a pointer to code (preferably an assembly code label). + For example, to create an entry for a handler whose code starts at + 0xDEADBEEF and that runs in privilege level 0 (therefore using the same + code segment selector as the kernel) the following two bytes would be + used: + 0xDEAD8E00 + 0x0008BEEF + + If the IDT is represented as an unsigned integer idt[512] then to + register the above example as an handler for interrupt 0 + (divide-by-zero), the following code would be used: + idt[0] = 0xDEAD8E00 + idt[1] = 0x0008BEEF + + As written in the chapter [160]"Getting to C", we recommend that you + instead of using bytes (or unsigned integers) use packed structures to + make the code more readable. + +6.3 Handling an Interrupt + + When an interrupt occurs the CPU will push some information about the + interrupt onto the stack, then look up the appropriate interrupt hander + in the IDT and jump to it. The stack at the time of the interrupt will + look like the following: + [esp + 12] eflags + [esp + 8] cs + [esp + 4] eip + [esp] error code? + + The reason for the question mark behind error code is that not all + interrupts create an error code. The specific CPU interrupts that put + an error code on the stack are 8, 10, 11, 12, 13, 14 and 17. The error + code can be used by the interrupt handler to get more information on + what has happened. Also, note that the interrupt number is not pushed + onto the stack. We can only determine what interrupt has occurred by + knowing what code is executing - if the handler registered for + interrupt 17 is executing, then interrupt 17 has occurred. + + Once the interrupt handler is done, it uses the iret instruction to + return. The instruction iret expects the stack to be the same as at the + time of the interrupt (see the figure above). Therefore, any values + pushed onto the stack by the interrupt handler must be popped. Before + returning, iret restores eflags by popping the value from the stack and + then finally jumps to cs:eip as specified by the values on the stack. + + The interrupt handler has to be written in assembly code, since all + registers that the interrupt handlers use must be preserved by pushing + them onto the stack. This is because the code that was interrupted + doesn't know about the interrupt and will therefore expect that its + registers stay the same. Writing all the logic of the interrupt handler + in assembly code will be tiresome. Creating a handler in assembly code + that saves the registers, calls a C function, restores the registers + and finally executes iret is a good idea! + + The C handler should get the state of the registers, the state of the + stack and the number of the interrupt as arguments. The following + definitions can for example be used: + struct cpu_state { + unsigned int eax; + unsigned int ebx; + unsigned int ecx; + . + . + . + unsigned int esp; + } __attribute__((packed)); + + struct stack_state { + unsigned int error_code; + unsigned int eip; + unsigned int cs; + unsigned int eflags; + } __attribute__((packed)); + + void interrupt_handler(struct cpu_state cpu, struct stack_state stack, unsig +ned int interrupt); + +6.4 Creating a Generic Interrupt Handler + + Since the CPU does not push the interrupt number on the stack it is a + little tricky to write a generic interrupt handler. This section will + use macros to show how it can be done. Writing one version for each + interrupt is tedious - it is better to use the macro functionality of + NASM [34]. And since not all interrupts produce an error code the value + 0 will be added as the "error code" for interrupts without an error + code. The following code shows an example of how this can be done: + %macro no_error_code_interrupt_handler %1 + global interrupt_handler_%1 + interrupt_handler_%1: + push dword 0 ; push 0 as error code + push dword %1 ; push the interrupt number + jmp common_interrupt_handler ; jump to the common handler + %endmacro + + %macro error_code_interrupt_handler %1 + global interrupt_handler_%1 + interrupt_handler_%1: + push dword %1 ; push the interrupt number + jmp common_interrupt_handler ; jump to the common handler + %endmacro + + common_interrupt_handler: ; the common parts of the generic in +terrupt handler + ; save the registers + push eax + push ebx + . + . + . + push ebp + + ; call the C function + call interrupt_handler + + ; restore the registers + pop ebp + . + . + . + pop ebx + pop eax + + ; restore the esp + add esp, 8 + + ; return to the code that got interrupted + iret + + no_error_code_interrupt_handler 0 ; create handler for interrupt 0 + no_error_code_interrupt_handler 1 ; create handler for interrupt 1 + . + . + . + error_code_handler 7 ; create handler for interrupt 7 + . + . + . + + The common_interrupt_handler does the following: + * Push the registers on the stack. + * Call the C function interrupt_handler. + * Pop the registers from the stack. + * Add 8 to esp (because of the error code and the interrupt number + pushed earlier). + * Execute iret to return to the interrupted code. + + Since the macros declare global labels the addresses of the interrupt + handlers can be accessed from C or assembly code when creating the IDT. + +6.5 Loading the IDT + + The IDT is loaded with the lidt assembly code instruction which takes + the address of the first element in the table. It is easiest to wrap + this instruction and use it from C: + global load_idt + + ; load_idt - Loads the interrupt descriptor table (IDT). + ; stack: [esp + 4] the address of the first entry in the IDT + ; [esp ] the return address + load_idt: + mov eax, [esp+4] ; load the address of the IDT into register eax + lidt eax ; load the IDT + ret ; return to the calling function + +6.6 Programmable Interrupt Controller (PIC) + + To start using hardware interrupts you must first configure the + Programmable Interrupt Controller (PIC). The PIC makes it possible to + map signals from the hardware to interrupts. The reasons for + configuring the PIC are: + * Remap the interrupts. The PIC uses interrupts 0 - 15 for hardware + interrupts by default, which conflicts with the CPU interrupts. + Therefore the PIC interrupts must be remapped to another interval. + * Select which interrupts to receive. You probably don't want to + receive interrupts from all devices since you don't have code that + handles these interrupts anyway. + * Set up the correct mode for the PIC. + + In the beginning there was only one PIC (PIC 1) and eight interrupts. + As more hardware were added, 8 interrupts were too few. The solution + chosen was to chain on another PIC (PIC 2) on the first PIC (see + interrupt 2 on PIC 1). + + The hardware interrupts are shown in the table below: + PIC 1 Hardware PIC 2 Hardware + 0 Timer 8 Real Time Clock + 1 Keyboard 9 General I/O + 2 PIC 2 10 General I/O + 3 COM 2 11 General I/O + 4 COM 1 12 General I/O + 5 LPT 2 13 Coprocessor + 6 Floppy disk 14 IDE Bus + 7 LPT 1 15 IDE Bus + + A great tutorial for configuring the PIC can be found at the SigOPS + website [35]. We won't repeat that information here. + + Every interrupt from the PIC has to be acknowledged - that is, sending + a message to the PIC confirming that the interrupt has been handled. If + this isn't done the PIC won't generate any more interrupts. + + Acknowledging a PIC interrupt is done by sending the byte 0x20 to the + PIC that raised the interrupt. Implementing a pic_acknowledge function + can thus be done as follows: + #include "io.h" + + #define PIC1_PORT_A 0x20 + #define PIC2_PORT_A 0xA0 + + /* The PIC interrupts have been remapped */ + #define PIC1_START_INTERRUPT 0x20 + #define PIC2_START_INTERRUPT 0x28 + #define PIC2_END_INTERRUPT PIC2_START_INTERRUPT + 7 + + #define PIC_ACK 0x20 + + /** pic_acknowledge: + * Acknowledges an interrupt from either PIC 1 or PIC 2. + * + * @param num The number of the interrupt + */ + void pic_acknowledge(unsigned integer interrupt) + { + if (interrupt < PIC1_START_INTERRUPT || interrupt > PIC2_END_INTERRUPT) +{ + return; + } + + if (interrupt < PIC2_START_INTERRUPT) { + outb(PIC1_PORT_A, PIC_ACK); + } else { + outb(PIC2_PORT_A, PIC_ACK); + } + } + +6.7 Reading Input from the Keyboard + + The keyboard does not generate ASCII characters, it generates scan + codes. A scan code represents a button - both presses and releases. The + scan code representing the just pressed button can be read from the + keyboard's data I/O port which has address 0x60. How this can be done + is shown in the following example: + #include "io.h" + + #define KBD_DATA_PORT 0x60 + + /** read_scan_code: + * Reads a scan code from the keyboard + * + * @return The scan code (NOT an ASCII character!) + */ + unsigned char read_scan_code(void) + { + return inb(KBD_DATA_PORT); + } + + The next step is to write a function that translates a scan code to the + corresponding ASCII character. If you want to map the scan codes to + ASCII characters as is done on an American keyboard then Andries + Brouwer has a great tutorial [36]. + + Remember, since the keyboard interrupt is raised by the PIC, you must + call pic_acknowledge at the end of the keyboard interrupt handler. + Also, the keyboard will not send you any more interrupts until you read + the scan code from the keyboard. + +6.8 Further Reading + + * The OSDev wiki has a great page on interrupts, + [161]http://wiki.osdev.org/Interrupts + * Chapter 6 of Intel Manual 3a [33] describes everything there is to + know about interrupts. + +7 The Road to User Mode + + Now that the kernel boots, prints to screen and reads from keyboard - + what do we do? Usually, a kernel is not supposed to do the application + logic itself, but leave that for applications. The kernel creates the + proper abstractions (for memory, files, devices) to make application + development easier, performs tasks on behalf of applications (system + calls) and [162]schedules processes. + + User mode, in contrast with kernel mode, is the environment in which + the user's programs execute. This environment is less privileged than + the kernel, and will prevent (badly written) user programs from messing + with other programs or the kernel. Badly written kernels are free to + mess up what they want. + + There's quite a way to go until the OS created in this book can execute + programs in user mode, but this chapter will show how to easily execute + a small program in kernel mode. + +7.1 Loading an External Program + + Where do we get the external program from? Somehow we need to load the + code we want to execute into memory. More feature-complete operating + systems usually have drivers and file systems that enable them to load + the software from a CD-ROM drive, a hard disk or other persistent + media. + + Instead of creating all these drivers and file systems we will use a + feature in GRUB called modules to load the program. + +7.1.1 GRUB Modules + + GRUB can load arbitrary files into memory from the ISO image, and these + files are usually referred to as modules. To make GRUB load a module, + edit the file iso/boot/grub/menu.lst and add the following line at the + end of the file: + module /modules/program + + Now create the folder iso/modules: + mkdir -p iso/modules + + The application program will be created later in this chapter. + + The code that calls kmain must be updated to pass information to kmain + about where it can find the modules. We also want to tell GRUB that it + should align all the modules on page boundaries when loading them (see + the chapter [163]"Paging" for details about page alignment). + + To instruct GRUB how to load our modules, the "multiboot header" - the + first bytes of the kernel - must be updated as follows: + ; in file `loader.s` + + + MAGIC_NUMBER equ 0x1BADB002 ; define the magic number constant + ALIGN_MODULES equ 0x00000001 ; tell GRUB to align modules + + ; calculate the checksum (all options + checksum should equal 0) + CHECKSUM equ -(MAGIC_NUMBER + ALIGN_MODULES) + + section .text: ; start of the text (code) section + align 4 ; the code must be 4 byte aligned + dd MAGIC_NUMBER ; write the magic number + dd ALIGN_MODULES ; write the align modules instruction + dd CHECKSUM ; write the checksum + + GRUB will also store a pointer to a struct in the register ebx that, + among other things, describes at which addresses the modules are + loaded. Therefore, you probably want to push ebx on the stack before + calling kmain to make it an argument for kmain. + +7.2 Executing a Program + +7.2.1 A Very Simple Program + + A program written at this stage can only perform a few actions. + Therefore, a very short program that writes a value to a register + suffices as a test program. Halting Bochs after a while and then check + that register contains the correct number by looking in the Bochs log + will verify that the program has run. This is an example of such a + short program: + ; set eax to some distinguishable number, to read from the log afterwards + mov eax, 0xDEADBEEF + + ; enter infinite loop, nothing more to do + ; $ means "beginning of line", ie. the same instruction + jmp $ + +7.2.2 Compiling + + Since our kernel cannot parse advanced executable formats we need to + compile the code into a flat binary. NASM can do this with the flag -f: + nasm -f bin program.s -o program + + This is all we need. You must now move the file program to the folder + iso/modules. + +7.2.3 Finding the Program in Memory + + Before jumping to the program we must find where it resides in memory. + Assuming that the contents of ebx is passed as an argument to kmain, we + can do this entirely from C. + + The pointer in ebx points to a multiboot structure [19]. Download the + multiboot.h file from + [164]http://www.gnu.org/software/grub/manual/multiboot/html_node/multib + oot.h.html, which describes the structure. + + The pointer passed to kmain in the ebx register can be cast to a + multiboot_info_t pointer. The address of the first module is in the + field mods_addr. The following code shows an example: + int kmain(/* additional arguments */ unsigned int ebx) + { + multiboot_info_t *mbinfo = (multiboot_info_t *) ebx; + unsigned int address_of_module = mbinfo->mods_addr; + } + + However, before just blindly following the pointer, you should check + that the module got loaded correctly by GRUB. This can be done by + checking the flags field of the multiboot_info_t structure. You should + also check the field mods_count to make sure it is exactly 1. For more + details about the multiboot structure, see the multiboot documentation + [19]. + +7.2.4 Jumping to the Code + + The only thing left to do is to jump to the code loaded by GRUB. Since + it is easier to parse the multiboot structure in C than assembly code, + calling the code from C is more convenient (it can of course be done + with jmp or call in assembly code as well). The C code could look like + this: + typedef void (*call_module_t)(void); + /* ... */ + call_module_t start_program = (call_module_t) address_of_module; + start_program(); + /* we'll never get here, unless the module code returns */ + + If we start the kernel, wait until it has run and entered the infinite + loop in the program, and then halt Bochs, we should see 0xDEADBEEF in + the register eax via the Bochs log. We have successfully started a + program in our OS! + +7.3 The Beginning of User Mode + + The program we've written now runs at the same privilege level as the + kernel - we've just entered it in a somewhat peculiar way. To enable + applications to execute at a different privilege level we'll need to, + beside [165]segmentation, do [166]paging and [167]page frame + allocation. + + It's quite a lot of work and technical details to go through, but in a + few chapters you'll have working user mode programs. + +8 A Short Introduction to Virtual Memory + + Virtual memory is an abstraction of physical memory. The purpose of + virtual memory is generally to simplify application development and to + let processes address more memory than what is actually physically + present in the machine. We also don't want applications messing with + the kernel or other applications' memory due to security. + + In the x86 architecture, virtual memory can be accomplished in two + ways: segmentation and paging. Paging is by far the most common and + versatile technique, and we'll implement it the next chapter. Some use + of segmentation is still necessary to allow for code to execute under + different privilege levels. + + Managing memory is a big part of what an operating system does. + [168]Paging and [169]page frame allocation deals with that. + + Segmentation and paging is described in the [33], chapter 3 and 4. + +8.1 Virtual Memory Through Segmentation? + + You could skip paging entirely and just use segmentation for virtual + memory. Each user mode process would get its own segment, with base + address and limit properly set up. This way no process can see the + memory of another process. A problem with this is that the physical + memory for a process needs to be contiguous (or at least it is very + convenient if it is). Either we need to know in advance how much memory + the program will require (unlikely), or we can move the memory segments + to places where they can grow when the limit is reached (expensive, + causes fragmentation - can result in "out of memory" even though enough + memory is available). Paging solves both these problems. + + It is interesting to note that in x86_64 (the 64-bit version of the x86 + architecture), segmentation is almost completely removed. + +8.2 Further Reading + + * LWN.net has an article on virtual memory: + [170]http://lwn.net/Articles/253361/ + * Gustavo Duarte has also written an article about virtual memory: + [171]http://duartes.org/gustavo/blog/post/memory-translation-and-se + gmentation + +9 Paging + + Segmentation translates a logical address into a linear address. Paging + translates these linear addresses onto the physical address space, and + determines access rights and how the memory should be cached. + +9.1 Why Paging? + + Paging is the most common technique used in x86 to enable virtual + memory. Virtual memory through paging means that each process will get + the impression that the available memory range is 0x00000000 - + 0xFFFFFFFF even though the actual size of the memory might be much + less. It also means that when a process addresses a byte of memory it + will use a virtual (linear) address instead of physical one. The code + in the user process won't notice any difference (except for execution + delays). The linear address gets translated to a physical address by + the MMU and the page table. If the virtual address isn't mapped to a + physical address, the CPU will raise a page fault interrupt. + + Paging is optional, and some operating systems do not make use of it. + But if we want to mark certain areas of memory accessible only to code + running at a certain privilege level (to be able to have processes + running at different privilege levels), paging is the neatest way to do + it. + +9.2 Paging in x86 + + Paging in x86 (chapter 4 in the Intel manual [33]) consists of a page + directory (PDT) that can contain references to 1024 page tables (PT), + each of which can point to 1024 sections of physical memory called page + frames (PF). Each page frame is 4096 byte large. In a virtual (linear) + address, the highest 10 bits specifies the offset of a page directory + entry (PDE) in the current PDT, the next 10 bits the offset of a page + table entry (PTE) within the page table pointed to by that PDE. The + lowest 12 bits in the address is the offset within the page frame to be + addressed. + + All page directories, page tables and page frames need to be aligned on + 4096 byte addresses. This makes it possible to address a PDT, PT or PF + with just the highest 20 bits of a 32 bit address, since the lowest 12 + need to be zero. + + The PDE and PTE structure is very similar to each other: 32 bits (4 + bytes), where the highest 20 bits points to a PTE or PF, and the lowest + 12 bits control access rights and other configurations. 4 bytes times + 1024 equals 4096 bytes, so a page directory and page table both fit in + a page frame themselves. + + The translation of linear addresses to physical addresses is described + in the figure below. + + While pages are normally 4096 bytes, it is also possible to use 4 MB + pages. A PDE then points directly to a 4 MB page frame, which needs to + be aligned on a 4 MB address boundary. The address translation is + almost the same as in the figure, with just the page table step + removed. It is possible to mix 4 MB and 4 KB pages. + Translating virtual addresses (linear addresses) to physical addresses. + + Translating virtual addresses (linear addresses) to physical addresses. + + The 20 bits pointing to the current PDT is stored in the register cr3. + The lower 12 bits of cr3 are used for configuration. + + For more details on the paging structures, see chapter 4 in the Intel + manual [33]. The most interesting bits are U/S, which determine what + privilege levels can access this page (PL0 or PL3), and R/W, which + makes the memory in the page read-write or read-only. + +9.2.1 Identity Paging + + The simplest kind of paging is when we map each virtual address onto + the same physical address, called identity paging. This can be done at + compile time by creating a page directory where each entry points to + its corresponding 4 MB frame. In NASM this can be done with macros and + commands (%rep, times and dd). It can of course also be done at + run-time by using ordinary assembly code instructions. + +9.2.2 Enabling Paging + + Paging is enabled by first writing the address of a page directory to + cr3 and then setting bit 31 (the PG "paging-enable" bit) of cr0 to 1. + To use 4 MB pages, set the PSE bit (Page Size Extensions, bit 4) of + cr4. The following assembly code shows an example: + ; eax has the address of the page directory + mov cr3, eax + + mov ebx, cr4 ; read current cr4 + or ebx, 0x00000010 ; set PSE + mov cr4, ebx ; update cr4 + + mov ebx, cr0 ; read current cr0 + or ebx, 0x80000000 ; set PG + mov cr0, ebx ; update cr0 + + ; now paging is enabled + +9.2.3 A Few Details + + It is important to note that all addresses within the page directory, + page tables and in cr3 need to be physical addresses to the structures, + never virtual. This will be more relevant in later sections where we + dynamically update the paging structures (see the chapter [172]"User + Mode"). + + An instruction that is useful when an updating a PDT or PT is invlpg. + It invalidates the Translation Lookaside Buffer (TLB) entry for a + virtual address. The TLB is a cache for translated addresses, mapping + physical addresses corresponding to virtual addresses. This is only + required when changing a PDE or PTE that was previously mapped to + something else. If the PDE or PTE had previously been marked as not + present (bit 0 was set to 0), executing invlpg is unnecessary. Changing + the value of cr3 will cause all entries in the TLB to be invalidated. + + An example of invalidating a TLB entry is shown below: + ; invalidate any TLB references to virtual address 0 + invlpg [0] + +9.3 Paging and the Kernel + + This section will describe how paging affects the OS kernel. We + encourage you to run your OS using identity paging before trying to + implement a more advanced paging setup, since it can be hard to debug a + malfunctioning page table that is set up via assembly code. + +9.3.1 Reasons to Not Identity Map the Kernel + + If the kernel is placed at the beginning of the virtual address space - + that is, the virtual address space (0x00000000, "size of kernel") maps + to the location of the kernel in memory - there will be issues when + linking the user mode process code. Normally, during linking, the + linker assumes that the code will be loaded into the memory position + 0x00000000. Therefore, when resolving absolute references, 0x00000000 + will be the base address for calculating the exact position. But if the + kernel is mapped onto the virtual address space (0x00000000, "size of + kernel"), the user mode process cannot be loaded at virtual address + 0x00000000 - it must be placed somewhere else. Therefore, the + assumption from the linker that the user mode process is loaded into + memory at position 0x00000000 is wrong. This can be corrected by using + a linker script which tells the linker to assume a different starting + address, but that is a very cumbersome solution for the users of the + operating system. + + This also assumes that we want the kernel to be part of the user mode + process' address space. As we will see later, this is a nice feature, + since during system calls we don't have to change any paging structures + to get access to the kernel's code and data. The kernel pages will of + course require privilege level 0 for access, to prevent a user process + from reading or writing kernel memory. + +9.3.2 The Virtual Address for the Kernel + + Preferably, the kernel should be placed at a very high virtual memory + address, for example 0xC0000000 (3 GB). The user mode process is not + likely to be 3 GB large, which is now the only way that it can conflict + with the kernel. When the kernel uses virtual addresses at 3 GB and + above it is called a higher-half kernel. 0xC0000000 is just an example, + the kernel can be placed at any address higher than 0 to get the same + benefits. Choosing the correct address depends on how much virtual + memory should be available for the kernel (it is easiest if all memory + above the kernel virtual address should belong to the kernel) and how + much virtual memory should be available for the process. + + If the user mode process is larger than 3 GB, some pages will need to + be swapped out by the kernel. Swapping pages is not part of this book. + +9.3.3 Placing the Kernel at 0xC0000000 + + To start with, it is better to place the kernel at 0xC0100000 than + 0xC0000000, since this makes it possible to map (0x00000000, + 0x00100000) to (0xC0000000, 0xC0100000). This way, the entire range + (0x00000000, "size of kernel") of memory is mapped to the range + (0xC0000000, 0xC0000000 + "size of kernel"). + + Placing the kernel at 0xC0100000 isn't hard, but it does require some + thought. This is once again a linking problem. When the linker resolves + all absolute references in the kernel, it will assume that our kernel + is loaded at physical memory location 0x00100000, not 0x00000000, since + relocation is used in the linker script (see the section [173]"Linking + the kernel"). However, we want the jumps to be resolved using + 0xC0100000 as base address, since otherwise a kernel jump will jump + straight into the user mode process code (remember that the user mode + process is loaded at virtual memory 0x00000000). + + However, we can't simply tell the linker to assume that the kernel + starts (is loaded) at 0xC01000000, since we want it to be loaded at the + physical address 0x00100000. The reason for having the kernel loaded at + 1 MB is because it can't be loaded at 0x00000000, since there is BIOS + and GRUB code loaded below 1 MB. Furthermore, we cannot assume that we + can load the kernel at 0xC0100000, since the machine might not have 3 + GB of physical memory. + + This can be solved by using both relocation (.=0xC0100000) and the AT + instruction in the linker script. Relocation specifies that + non-relative memory-references should should use the relocation address + as base in address calculations. AT specifies where the kernel should + be loaded into memory. Relocation is done at link time by GNU ld [37], + the load address specified by AT is handled by GRUB when loading the + kernel, and is part of the ELF format [18]. + +9.3.4 Higher-half Linker Script + + We can modify the [174]first linker script to implement this: + ENTRY(loader) /* the name of the entry symbol */ + + . = 0xC0100000 /* the code should be relocated to 3GB + 1MB */ + + /* align at 4 KB and load at 1 MB */ + .text ALIGN (0x1000) : AT(ADDR(.text)-0xC0000000) + { + *(.text) /* all text sections from all files */ + } + + /* align at 4 KB and load at 1 MB + . */ + .rodata ALIGN (0x1000) : AT(ADDR(.text)-0xC0000000) + { + *(.rodata*) /* all read-only data sections from all files */ + } + + /* align at 4 KB and load at 1 MB + . */ + .data ALIGN (0x1000) : AT(ADDR(.text)-0xC0000000) + { + *(.data) /* all data sections from all files */ + } + + /* align at 4 KB and load at 1 MB + . */ + .bss ALIGN (0x1000) : AT(ADDR(.text)-0xC0000000) + { + *(COMMON) /* all COMMON sections from all files */ + *(.bss) /* all bss sections from all files */ + } + +9.3.5 Entering the Higher Half + + When GRUB jumps to the kernel code, there is no paging table. + Therefore, all references to 0xC0100000 + X won't be mapped to the + correct physical address, and will therefore cause a general protection + exception (GPE) at the very best, otherwise (if the computer has more + than 3 GB of memory) the computer will just crash. + + Therefore, assembly code that doesn't use relative jumps or relative + memory addressing must be used to do the following: + * Set up a page table. + * Add identity mapping for the first 4 MB of the virtual address + space. + * Add an entry for 0xC0100000 that maps to 0x0010000 + + If we skip the identity mapping for the first 4 MB, the CPU would + generate a page fault immediately after paging was enabled when trying + to fetch the next instruction from memory. After the table has been + created, an jump can be done to a label to make eip point to a virtual + address in the higher half: + ; assembly code executing at around 0x00100000 + ; enable paging for both actual location of kernel + ; and its higher-half virtual location + + lea ebx, [higher_half] ; load the address of the label in ebx + jmp ebx ; jump to the label + + higher_half: + ; code here executes in the higher half kernel + ; eip is larger than 0xC0000000 + ; can continue kernel initialisation, calling C code, etc. + + The register eip will now point to a memory location somewhere right + after 0xC0100000 - all the code can now execute as if it were located + at 0xC0100000, the higher-half. The entry mapping of the first 4 MB of + virtual memory to the first 4 MB of physical memory can now be removed + from the page table and its corresponding entry in the TLB invalidated + with invlpg [0]. + +9.3.6 Running in the Higher Half + + There are a few more details we must deal with when using a higher-half + kernel. We must be careful when using memory-mapped I/O that uses + specific memory locations. For example, the frame buffer is located at + 0x000B8000, but since there is no entry in the page table for the + address 0x000B8000 any longer, the address 0xC00B8000 must be used, + since the virtual address 0xC0000000 maps to the physical address + 0x00000000. + + Any explicit references to addresses within the multiboot structure + needs to be changed to reflect the new virtual addresses as well. + + Mapping 4 MB pages for the kernel is simple, but wastes memory (unless + you have a really big kernel). Creating a higher-half kernel mapped in + as 4 KB pages saves memory but is harder to set up. Memory for the page + directory and one page table can be reserved in the .data section, but + one needs to configure the mappings from virtual to physical addresses + at run-time. The size of the kernel can be determined by exporting + labels from the linker script [37], which we'll need to do later anyway + when writing the page frame allocator (see the chapter [175]"Page Frame + Allocation). + +9.4 Virtual Memory Through Paging + + Paging enables two things that are good for virtual memory. First, it + allows for fine-grained access control to memory. You can mark pages as + read-only, read-write, only for PL0 etc. Second, it creates the + illusion of contiguous memory. User mode processes, and the kernel, can + access memory as if it were contiguous, and the contiguous memory can + be extended without the need to move data around in memory. We can also + allow the user mode programs access to all memory below 3 GB, but + unless they actually use it, we don't have to assign page frames to the + pages. This allows processes to have code located near 0x00000000 and + the stack at just below 0xC0000000, and still not require more than two + actual pages. + +9.5 Further Reading + + * Chapter 4 (and to some extent chapter 3) of the Intel manual [33] + are your definitive sources for the details about paging. + * Wikipedia has an article on paging: + [176]http://en.wikipedia.org/wiki/Paging + * The OSDev wiki has a page on paging: + [177]http://wiki.osdev.org/Paging and a tutorial for making a + higher-half kernel: + [178]http://wiki.osdev.org/Higher_Half_bare_bones + * Gustavo Duarte's article on how a kernel manages memory is well + worth a read: + [179]http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-m + emory + * Details on the linker command language can be found at Steve + Chamberlain's website [37]. + * More details on the ELF format can be found in this presentation: + [180]http://flint.cs.yale.edu/cs422/doc/ELF_Format.pdf + +10 Page Frame Allocation + + When using virtual memory, how does the OS know which parts of memory + are free to use? That is the role of the page frame allocator. + +10.1 Managing Available Memory + +10.1.1 How Much Memory is There? + + First we need to know how much memory is available on the computer the + OS is running on. The easiest way to do this is to read it from the + multiboot structure [19] passed to us by GRUB. GRUB collects the + information we need about the memory - what is reserved, I/O mapped, + read-only etc. We must also make sure that we don't mark the part of + memory used by the kernel as free (since GRUB doesn't mark this memory + as reserved). One way to know how much memory the kernel uses is to + export labels at the beginning and the end of the kernel binary from + the linker script: + ENTRY(loader) /* the name of the entry symbol */ + + . = 0xC0100000 /* the code should be relocated to 3 GB + 1 MB */ + + /* these labels get exported to the code files */ + kernel_virtual_start = .; + kernel_physical_start = . - 0xC0000000; + + /* align at 4 KB and load at 1 MB */ + .text ALIGN (0x1000) : AT(ADDR(.text)-0xC0000000) + { + *(.text) /* all text sections from all files */ + } + + /* align at 4 KB and load at 1 MB + . */ + .rodata ALIGN (0x1000) : AT(ADDR(.rodata)-0xC0000000) + { + *(.rodata*) /* all read-only data sections from all files */ + } + + /* align at 4 KB and load at 1 MB + . */ + .data ALIGN (0x1000) : AT(ADDR(.data)-0xC0000000) + { + *(.data) /* all data sections from all files */ + } + + /* align at 4 KB and load at 1 MB + . */ + .bss ALIGN (0x1000) : AT(ADDR(.bss)-0xC0000000) + { + *(COMMON) /* all COMMON sections from all files */ + *(.bss) /* all bss sections from all files */ + } + + kernel_virtual_end = .; + kernel_physical_end = . - 0xC0000000; + + These labels can directly be read from assembly code and pushed on the + stack to make them available to C code: + extern kernel_virtual_start + extern kernel_virtual_end + extern kernel_physical_start + extern kernel_physical_end + + ; ... + + push kernel_physical_end + push kernel_physical_start + push kernel_virtual_end + push kernel_virtual_start + + call kmain + + This way we get the labels as arguments to kmain. If you want to use C + instead of assembly code, one way to do it is to declare the labels as + functions and take the addresses of these functions: + void kernel_virtual_start(void); + + /* ... */ + + unsigned int vaddr = (unsigned int) &kernel_virtual_start; + + If you use GRUB modules you need to make sure the memory they use is + marked as reserved as well. + + Note that the available memory does not need to be contiguous. In the + first 1 MB there are several I/O-mapped memory sections, as well as + memory used by GRUB and the BIOS. Other parts of the memory might be + similarly unavailable. + + It's convenient to divide the memory sections into complete page + frames, as we can't map part of pages into memory. + +10.1.2 Managing Available Memory + + How do we know which page frames are in use? The page frame allocator + needs to keep track of which are free and which aren't. There are + several ways to do this: bitmaps, linked lists, trees, the Buddy System + (used by Linux) etc. For more information about the different + algorithms see the article on OSDev [38]. + + Bitmaps are quite easy to implement. One bit is used for each page + frame and one (or more) page frames are dedicated to store the bitmap. + (Note that this is just one way to do it, other designs might be better + and/or more fun to implement.) + +10.2 How Can We Access a Page Frame? + + The page frame allocator returns the physical start address of the page + frame. This page frame is not mapped in - no page table points to this + page frame. How can we read and write data to the frame? + + We need to map the page frame into virtual memory, by updating the PDT + and/or PT used by the kernel. What if all available page tables are + full? Then we can't map the page frame into memory, because we'd need a + new page table - which takes up an entire page frame - and to write to + this page frame we'd need to map its page frame... Somehow this + circular dependency must be broken. + + One solution is to reserve a part of the first page table used by the + kernel (or some other higher-half page table) for temporarily mapping + page frames to make them accessible. If the kernel is mapped at + 0xC0000000 (page directory entry with index 768), and 4 KB page frames + are used, then the kernel has at least one page table. If we assume - + or limit us to - a kernel of size at most 4 MB minus 4 KB we can + dedicate the last entry (entry 1023) of this page table for temporary + mappings. The virtual address of pages mapped in using the last entry + of the kernel's PT will be: + (768 << 22) | (1023 << 12) | 0x000 = 0xC03FF000 + + After we've temporarily mapped the page frame we want to use as a page + table, and set it up to map in our first page frame, we can add it to + the paging directory, and remove the temporary mapping. + +10.3 A Kernel Heap + + So far we've only been able to work with fixed-size data, or directly + with raw memory. Now that we have a page frame allocator we can + implement malloc and free to use in the kernel. + + Kernighan and Ritchie [8] have an example implementation in their book + [8] that we can draw inspiration from. The only modification we need to + do is to replace calls to sbrk/brk with calls to the page frame + allocator when more memory is needed. We must also make sure to map the + page frames returned by the page frame allocator to virtual addresses. + A correct implementation should also return page frames to the page + frame allocator on call to free, whenever sufficiently large blocks of + memory are freed. + +10.4 Further reading + + * The OSDev wiki page on page frame allocation: + [181]http://wiki.osdev.org/Page_Frame_Allocation + +11 User Mode + + User mode is now almost within our reach, there are just a few more + steps required to get there. Although these steps might seem easy they + way they are presented in this chapter, they can be tricky to + implement, since there are a lot of places where small errors will + cause bugs that are hard to find. + +11.1 Segments for User Mode + + To enable user mode we need to add two more segments to the GDT. They + are very similar to the kernel segments we added when we [182]set up + the GDT in the [183]chapter about segmentation: + + CAPTION: The segment descriptors needed for user mode. + + Index Offset Name Address range Type DPL + 3 0x18 user code segment 0x00000000 - 0xFFFFFFFF RX PL3 + 4 0x20 user data segment 0x00000000 - 0xFFFFFFFF RW PL3 + + The difference is the DPL, which now allows code to execute in PL3. The + segments can still be used to address the entire address space, just + using these segments for user mode code will not protect the kernel. + For that we need paging. + +11.2 Setting Up For User Mode + + There are a few things every user mode process needs: + * Page frames for code, data and stack. At the moment it suffices to + allocate one page frame for the stack and enough page frames to fit + the program's code. Don't worry about setting up a stack that can + be grow and shrink at this point in time, focus on getting a basic + implementation work first. + * The binary from the GRUB module has to be copied to the page frames + used for the programs code. + * A page directory and page tables are needed to map the page frames + described above into memory. At least two page tables are needed, + because the code and data should be mapped in at 0x00000000 and + increasing, and the stack should start just below the kernel, at + 0xBFFFFFFB, growing towards lower addresses. The U/S flag has to be + set to allow PL3 access. + + It might be convenient to store this information in a struct + representing a process. This process struct can be dynamically + allocated with the kernel's malloc function. + +11.3 Entering User Mode + + The only way to execute code with a lower privilege level than the + current privilege level (CPL) is to execute an iret or lret instruction + - interrupt return or long return, respectively. + + To enter user mode we set up the stack as if the processor had raised + an inter-privilege level interrupt. The stack should look like the + following: + [esp + 16] ss ; the stack segment selector we want for user mode + [esp + 12] esp ; the user mode stack pointer + [esp + 8] eflags ; the control flags we want to use in user mode + [esp + 4] cs ; the code segment selector + [esp + 0] eip ; the instruction pointer of user mode code to execute + + See the Intel manual [33], section 6.2.1, figure 6-4 for more + information. + + The instruction iret will then read these values from the stack and + fill in the corresponding registers. Before we execute iret we need to + change to the page directory we setup for the user mode process. It is + important to remember that to continue executing kernel code after + we've switched PDT, the kernel needs to be mapped in. One way to + accomplish this is to have a separate PDT for the kernel, which maps + all data at 0xC0000000 and above, and merge it with the user PDT (which + only maps below 0xC0000000) when performing the switch. Remember that + physical address of the PDT has to be used when setting the register + cr3. + + The register eflags contains a set of different flags, specified in + section 2.3 of the Intel manual [33]. Most important for us is the + interrupt enable (IF) flag. The assembly code instruction sti can't be + used in privilege level 3 for enabling interrupts. If interrupts are + disabled when entering user mode, then interrupts can't enabled once + user mode is entered. Setting the IF flag in the eflags entry on the + stack will enable interrupts in user mode, since the assembly code + instruction iret will set the register eflags to the corresponding + value on the stack. + + For now, we should have interrupts disabled, as it requires a little + more work to get inter-privilege level interrupts to work properly (see + the section [184]"System calls"). + + The value eip on the stack should point to the entry point for the user + code - 0x00000000 in our case. The value esp on the stack should be + where the stack starts - 0xBFFFFFFB (0xC0000000 - 4). + + The values cs and ss on the stack should be the segment selectors for + the user code and user data segments, respectively. As we saw in the + [185]segmentation chapter, the lowest two bits of a segment selector is + the RPL - the Requested Privilege Level. When using iret to enter PL3, + the RPL of cs and ss should be 0x3. The following code shows an + example: + USER_MODE_CODE_SEGMENT_SELECTOR equ 0x18 + USER_MODE_DATA_SEGMENT_SELECTOR equ 0x20 + mov cs, USER_MODE_CODE_SEGMENT_SELECTOR | 0x3 + mov ss, USER_MODE_DATA_SEGMENT_SELECTOR | 0x3 + + The register ds, and the other data segment registers, should be set to + the same segment selector as ss. They can be set the ordinary way, with + the mov assembly code instruction. + + We are now ready to execute iret. If everything has been set up right, + we should now have a kernel that can enter user mode. + +11.4 Using C for User Mode Programs + + When C is used as the programming language for user mode programs, it + is important to think about the structure of the file that will be the + result of the compilation. + + The reason we can use ELF [18] as the file format for for the kernel + executable is because GRUB knows how to parse and interpret the ELF + file format. If we implemented an ELF parser, we could compile the user + mode programs into ELF binaries as well. We leave this as an exercise + for the reader. + + One thing we can do to make it easier to develop user mode programs is + to allow the programs to be written in C, but compile them to flat + binaries instead of ELF binaries. In C the layout of the generated code + is more unpredictable and the entry point, main, might not be at offset + 0 in the binary. One common way to work around this is to add a few + assembly code lines placed at offset 0 which calls main: + extern main + + section .text + ; push argv + ; push argc + call main + ; main has returned, eax is return value + jmp $ ; loop forever + + If this code is saved in a file called start.s, then the following code + show an example of a linker script that places these instructions first + in executable (remember that start.s gets compiled to start.o): + OUTPUT_FORMAT("binary") /* output flat binary */ + + SECTIONS + { + . = 0; /* relocate to address 0 */ + + .text ALIGN(4): + { + start.o(.text) /* include the .text section of start.o */ + *(.text) /* include all other .text sections */ + } + + .data ALIGN(4): + { + *(.data) + } + + .rodata ALIGN(4): + { + *(.rodata*) + } + } + + Note: *(.text) will not include the .text section of start.o again. + + With this script we can write programs in C or assembler (or any other + language that compiles to object files linkable with ld), and it is + easy to load and map for the kernel (.rodata will be mapped in as + writeable, though). + + When we compile user programs we want the following GCC flags: + -m32 -nostdlib -nostdinc -fno-builtin -fno-stack-protector -nostartfiles + -nodefaultlibs + + For linking, the followings flags should be used: + -T link.ld -melf_i386 # emulate 32 bits ELF, the binary output is specified + # in the linker script + + The option -T instructs the linker to use the linker script link.ld. + +11.4.1 A C Library + + It might now be interesting to start thinking about writing a small + "standard library" for your programs. Some of the functionality + requires [186]system calls to work, but some, such as the functions in + string.h, does not. + +11.5 Further Reading + + * Gustavo Duarte has an article on privilege levels: + [187]http://duartes.org/gustavo/blog/post/cpu-rings-privilege-and-p + rotection + +12 File Systems + + We are not required to have file systems in our operating system, but + it is a very usable abstraction, and it often plays a central part of + many operating systems, especially UNIX-like operating systems. Before + we start the process of supporting multiple processes and system calls + we might want to consider implementing a simple file system. + +12.1 Why a File System? + + How do we specify what programs to run in our OS? Which is the first + program to run? How do programs output data or read input? + + In UNIX-like systems, with their almost-everything-is-a-file + convention, these problems are solved by the file system. (It might + also be interesting to read a bit about the Plan 9 project, which takes + this idea one step further.) + +12.2 A Simple Read-Only File System + + The simplest file system might be what we already have - one file, + existing only in RAM, loaded by GRUB before the kernel starts. When the + kernel and operating system grows this is probably too limiting. + + A file system that is slightly more advanced than just the bits of one + file is a file with metadata. The metadata can describe the type of the + file, the size of the file and so on. A utility program can be created + that runs at build time, adding this metadata to a file. This way, a + "file system in a file" can be constructed by concatenating several + files with metadata into one large file. The result of this technique + is a read-only file system that resides in memory (once GRUB has loaded + the file). + + The program constructing the file system can traverse a directory on + the host system and add all subdirectories and files as part of the + target file system. Each object in the file system (directory or file) + can consist of a header and a body, where the body of a file is the + actual file and the body of a directory is a list of entries - names + and "addresses" of other files and directories. + + Each object in this file system will become contiguous, so they will be + easy to read from memory for the kernel. All objects will also have a + fixed size (except for the last one, which can grow), therefore it is + difficult to add new files or modify existing ones. + +12.3 Inodes and Writable File Systems + + When the need for a writable file system arises, then it is a good idea + to look into the concept of an inode. See the section [188]"Further + Reading" for recommended reading. + +12.4 A Virtual File System + + What abstraction should be used for reading and writing to devices such + as the screen and the keyboard? + + A virtual file system (VFS) creates an abstraction on top of the + concrete file systems. A VFS mainly supplies the path system and file + hierarchy, it delegates operations on files to the underlying file + systems. The original paper on VFS is succinct and well worth a read. + See the section [189]"Further Reading" for a reference. + + With a VFS we could mount a special file system on the path /dev. This + file system would handle all devices such as keyboards and the console. + However, one could also take the traditional UNIX approach, with + major/minor device numbers and mknod to create special files for + devices. Which approach you think is the most appropriate is up to you, + there is no right or wrong when building abstraction layers (although + some abstractions turn out way more useful than others). + +12.5 Further Reading + + * The ideas behind the Plan 9 operating systems is worth taking a + look at: [190]http://plan9.bell-labs.com/plan9/index.html + * Wikipedia's page on inodes: [191]http://en.wikipedia.org/wiki/Inode + and the inode pointer structure: + [192]http://en.wikipedia.org/wiki/Inode_pointer_structure. + * The original paper on the concept of vnodes and a virtual file + system is quite interesting: + [193]http://www.arl.wustl.edu/~fredk/Courses/cs523/fall01/Papers/kl + eiman86vnodes.pdf + * Poul-Henning Kamp discusses the idea of a special file system for + /dev in + [194]http://static.usenix.org/publications/library/proceedings/bsdc + on02/full_papers/kamp/kamp_html/index.html + +13 System Calls + + System calls is the way user-mode applications interact with the kernel + - to ask for resources, request operations to be performed, etc. The + system call API is the part of the kernel that is most exposed to the + users, therefore its design requires some thought. + +13.1 Designing System Calls + + It is up to us, the kernel developers, to design the system calls that + application developers can use. We can draw inspiration from the POSIX + standards or, if they seem like too much work, just look at the ones + for Linux, and pick and choose. See the section [195]"Further Reading" + at the end of the chapter for references. + +13.2 Implementing System Calls + + System calls are traditionally invoked with software interrupts. The + user applications put the appropriate values in registers or on the + stack and then initiates a pre-defined interrupt which transfers + execution to the kernel. The interrupt number used is dependent on the + kernel, Linux uses the number 0x80 to identify that an interrupt is + intended as a system call. + + When system calls are executed, the current privilege level is + typically changed from PL3 to PL0 (if the application is running in + user mode). To allow this, the DPL of the entry in the IDT for the + system call interrupt needs to allow PL3 access. + + Whenever inter-privilege level interrupts occur, the processor pushes a + few important registers onto the stack - the same ones we used to enter + user mode [196]before, see figure 6-4, section 6.12.1, in the Intel + manual [33]. What stack is used? The same section in [33] specifies + that if an interrupt leads to code executing at a numerically lower + privilege level, a stack switch occurs. The new values for the + registers ss and esp is loaded from the current Task State Segment + (TSS). The TSS structure is specified in figure 7-2, section 7.2.1 of + the Intel manual [33]. + + To enable system calls we need to setup a TSS before entering user + mode. Setting it up can be done in C by setting the ss0 and esp0 fields + of a "packed struct" that represents a TSS. Before loading the "packed + struct" into the processor, a TSS descriptor has to be added to the + GDT. The structure of the TSS descriptor is described in section 7.2.2 + in [33]. + + You specify the current TSS segment selector by loading it into the tr + register with the ltr assembly code instruction. If the TSS segment + descriptor has index 5, and thus offset 5 * 8 = 40 = 0x28, this is the + value that should be loaded into the register tr. + + When we entered user mode before in the chapter [197]"Entering User + Mode" we disabled interrupts when executing in PL3. Since system calls + are implemented using interrupts, interrupts must be enabled in user + mode. Setting the IF flag bit in the eflags value on the stack will + make iret enable interrupts (since the eflags value on the stack will + be loaded into the eflags register by the assembly code instruction + iret). + +13.3 Further Reading + + * The Wikipedia page on POSIX, with links to the specifications: + [198]http://en.wikipedia.org/wiki/POSIX + * A list of system calls used in Linux: + [199]http://bluemaster.iu.hio.no/edu/dark/lin-asm/syscalls.html + * The Wikipedia page on system calls: + [200]http://en.wikipedia.org/wiki/System_call + * The Intel manual [33] sections on interrupts (chapter 6) and TSS + (chapter 7) are where you get all the details you need. + +14 Multitasking + + How do you make multiple processes appear to run at the same time? + Today, this question has two answers: + * With the availability of multi-core processors, or on system with + multiple processors, two processes can actually run at the same + time by running two processes on different cores or processors. + * Fake it. That is, switch rapidly (faster than a human can notice) + between the processes. At any given moment there is only one + process executing, but the rapid switching gives the impression + that they are running "at the same time". + + Since the operating system created in this book does not support + multi-core processors or multiple processors the only option is to fake + it. The part of the operating system responsible for rapidly switching + between the processes is called the scheduling algorithm. + +14.1 Creating New Processes + + Creating new processes is usually done with two different system calls: + fork and exec. fork creates an exact copy of the currently running + process, while exec replaces the current process with one that is + specified by a path to the location of a program in the file system. Of + these two we recommend that you start implementing exec, since this + system call will do almost exactly the same steps as described in the + section [201]"Setting up for user mode" in the chapter [202]"User + Mode". + +14.2 Cooperative Scheduling with Yielding + + The easiest way to achieve rapid switching between processes is if the + processes themselves are responsible for the switching. The processes + run for a while and then tell the OS (via a system call) that it can + now switch to another process. Giving up the control of CPU to another + process is called yielding and when the processes themselves are + responsible for the scheduling it's called cooperative scheduling, + since all the processes must cooperate with each other. + + When a process yields the process' entire state must be saved (all the + registers), preferably on the kernel heap in a structure that + represents a process. When changing to a new process all the registers + must be restored from the saved values. + + Scheduling can be implemented by keeping a list of which processes are + running. The system call yield should then run the next process in the + list and put the current one last (other schemes are possible, but this + is a simple one). + + The transfer of control to the new process is done via the iret + assembly code instruction in exactly the same way as explained in the + section [203]"Entering user mode" in the chapter [204]"User Mode". + + We strongly recommend that you start to implement support for multiple + processes by implementing cooperative scheduling. We further recommend + that you have a working solution for both exec, fork and yield before + implementing preemptive scheduling. Since cooperative scheduling is + deterministic, it is much easier to debug than preemptive scheduling. + +14.3 Preemptive Scheduling with Interrupts + + Instead of letting the processes themselves manage when to change to + another process the OS can switch processes automatically after a short + period of time. The OS can set up the programmable interval timer (PIT) + to raise an interrupt after a short period of time, for example 20 ms. + In the interrupt handler for the PIT interrupt the OS will change the + running process to a new one. This way the processes themselves don't + need to worry about scheduling. This kind of scheduling is called + preemptive scheduling. + +14.3.1 Programmable Interval Timer + + To be able to do preemptive scheduling the PIT must first be configured + to raise interrupts every x milliseconds, where x should be + configurable. + + The configuration of the PIT is very similar to the configuration of + other hardware devices: a byte is sent to an I/O port. The command port + of the PIT is 0x43. To read about all the configuration options, see + the article about the PIT on OSDev [39]. We use the following options: + * Raise interrupts (use channel 0) + * Send the divider as low byte then high byte (see next section for + an explanation) + * Use a square wave + * Use binary mode + + This results in the configuration byte 00110110. + + Setting the interval for how often interrupts are to be raised is done + via a divider, the same way as for the serial port. Instead of sending + the PIT a value (e.g. in milliseconds) that says how often an interrupt + should be raised you send the divider. The PIT operates at 1193182 Hz + as default. Sending the divider 10 results in the PIT running at + 1193182 / 10 = 119318 Hz. The divider can only be 16 bits, so it is + only possible to configure the timer's frequency between 1193182 Hz and + 1193182 / 65535 = 18.2 Hz. We recommend that you create a function that + takes an interval in milliseconds and converts it to the correct + divider. + + The divider is sent to the channel 0 data I/O port of the PIT, but + since only one byte can be sent at at a time, the lowest 8 bits of the + divider has to sent first, then the highest 8 bits of the divider can + be sent. The channel 0 data I/O port is located at 0x40. Again, see the + article on OSDev [39] for more details. + +14.3.2 Separate Kernel Stacks for Processes + + If all processes uses the same kernel stack (the stack exposed by the + TSS) there will be trouble if a process is interrupted while still in + kernel mode. The process that is being switched to will now use the + same kernel stack and will overwrite what the previous process have + written on the stack (remember that TSS data structure points to the + beginning of the stack). + + To solve this problem every process should have it's own kernel stack, + the same way that each process have their own user mode stack. When + switching process the TSS must be updated to point to the new process' + kernel stack. + +14.3.3 Difficulties with Preemptive Scheduling + + When using preemptive scheduling one problem arises that doesn't exist + with cooperative scheduling. With cooperative scheduling every time a + process yields, it must be in user mode (privilege level 3), since + yield is a system call. With preemptive scheduling, the processes can + be interrupted in either user mode or kernel mode (privilege level 0), + since the process itself does not control when it gets interrupted. + + Interrupting a process in kernel mode is a little bit different than + interrupting a process in user mode, due to the way the CPU sets up the + stack at interrupts. If a privilege level change occurred (the process + was interrupted in user mode) the CPU will push the value of the + process ss and esp register on the stack. If no privilege level change + occurs (the process was interrupted in kernel mode) the CPU won't push + the esp register on the stack. Furthermore, if there was no privilege + level change, the CPU won't change stack to the one defined it the TSS. + + This problem is solved by calculating what the value of esp was before + the interrupt. Since you know that the CPU pushes 3 things on the stack + when no privilege change happens and you know how much you have pushed + on the stack, you can calculate what the value of esp was at the time + of the interrupt. This is possible since the CPU won't change stacks if + there is no privilege level change, so the content of esp will be the + same as at the time of the interrupt. + + To further complicate things, one must think of how to handle case when + switching to a new process that should be running in kernel mode. Since + iret is being used without a privilege level change the CPU won't + update the value of esp with the one placed on the stack - you must + update esp yourself. + +14.4 Further Reading + + * For more information about different scheduling algorithms, see + [205]http://wiki.osdev.org/Scheduling_Algorithms + +14.4 References + + [1] Andrew Tanenbaum, 2007. Modern operating systems, 3rd edition. + Prentice Hall, Inc., + + [2] The royal institute of technology, [206]http://www.kth.se, + + [3] Wikipedia, Hexadecimal, + [207]http://en.wikipedia.org/wiki/Hexadecimal, + + [4] OSDev, OSDev, [208]http://wiki.osdev.org/Main_Page, + + [5] James Molloy, James m's kernel development tutorial, + [209]http://www.jamesmolloy.co.uk/tutorial_html/, + + [6] Canonical Ltd, Ubuntu, [210]http://www.ubuntu.com/, + + [7] Oracle, Oracle vM virtualBox, [211]http://www.virtualbox.org/, + + [8] Dennis M. Ritchie Brian W. Kernighan, 1988. The c programming + language, second edition. Prentice Hall, Inc., + + [9] Wikipedia, C (programming language), + [212]http://en.wikipedia.org/wiki/C_(programming_language), + + [10] Free Software Foundation, GCC, the gNU compiler collection, + [213]http://gcc.gnu.org/, + + [11] NASM, NASM: The netwide assembler, [214]http://www.nasm.us/, + + [12] Wikipedia, Bash, + [215]http://en.wikipedia.org/wiki/Bash_%28Unix_shell%29, + + [13] Free Software Foundation, GNU make, + [216]http://www.gnu.org/software/make/, + + [14] Volker Ruppert, bochs: The open souce iA-32 emulation project, + [217]http://bochs.sourceforge.net/, + + [15] QEMU, QEMU, [218]http://wiki.qemu.org/Main_Page, + + [16] Wikipedia, BIOS, [219]https://en.wikipedia.org/wiki/BIOS, + + [17] Free Software Foundation, GNU gRUB, + [220]http://www.gnu.org/software/grub/, + + [18] Wikipedia, Executable and linkable format, + [221]http://en.wikipedia.org/wiki/Executable_and_Linkable_Format, + + [19] Free Software Foundation, Multiboot specification version 0.6.96, + [222]http://www.gnu.org/software/ grub/manual/multiboot/multiboot.html, + + [20] GNU, GNU binutils, [223]http://www.gnu.org/software/binutils/, + + [21] Lars Nodeen, Bug #426419: configure: error: GRUB requires a + working absolute objcopy, + [224]https://bugs.launchpad.net/ubuntu/+source/grub/+bug/426419, + + [22] Wikipedia, ISO image, [225]http://en.wikipedia.org/wiki/ISO_image, + + [23] Bochs, bochsrc, + [226]http://bochs.sourceforge.net/doc/docbook/user/bochsrc.html, + + [24] NASM, RESB and friends: Declaring uninitialized data, + [227]http://www.nasm.us/doc/nasmdoc3.htm, + + [25] Wikipedia, x86 calling conventions, + [228]http://en.wikipedia.org/wiki/X86_calling_conventions, + + [26] Wikipedia, Framebuffer, + [229]http://en.wikipedia.org/wiki/Framebuffer, + + [27] Wikipedia, VGA-compatible text mode, + [230]http://en.wikipedia.org/wiki/VGA-compatible_text_mode, + + [28] Wikipedia, ASCII, [231]https://en.wikipedia.org/wiki/Ascii, + + [29] OSDev, VGA hardware, [232]http://wiki.osdev.org/VGA_Hardware, + + [30] Wikipedia, Serial port, + [233]http://en.wikipedia.org/wiki/Serial_port, + + [31] OSDev, Serial ports, [234]http://wiki.osdev.org/Serial_ports, + + [32] WikiBooks, Serial programming/8250 uART programming, + [235]http://en.wikibooks.org/wiki/Serial_Programming/ + 8250_UART_Programming, + + [33] Intel, Intel 64 and iA-32 architectures software developer's + manual vol. 3A, [236]http://www.intel.com/content/ + www/us/en/architecture-and-technology/64-ia-32-architectures-software-d + eveloper-vol-3a-part-1-manual.html/, + + [34] NASM, Multi-line macros, + [237]http://www.nasm.us/doc/nasmdoc4.html#section-4.3, + + [35] SIGOPS, i386 interrupt handling, + [238]http://www.acm.uiuc.edu/sigops/roll_your_own/i386/irq.html, + + [36] Andries Brouwer, Keyboard scancodes, [239]http://www.win.tue.nl/, + + [37] Steve Chamberlain, Using ld, the gNU linker, + [240]http://www.math.utah.edu/docs/info/ld_toc.html, + + [38] OSDev, Page frame allocation, + [241]http://wiki.osdev.org/Page_Frame_Allocation, + + [39] OSDev, Programmable interval timer, + [242]http://wiki.osdev.org/Programmable_Interval_Timer, + __________________________________________________________________ + + 1. The bootloader must fit into the master boot record (MBR) boot + sector of a hard drive, which is only 512 bytes large.[243]© + +References + + 1. https://github.com/littleosbook/littleosbook/ + 2. https://littleosbook.github.io/book.pdf + 3. https://littleosbook.github.io/#introduction + 4. https://littleosbook.github.io/#about-the-book + 5. https://littleosbook.github.io/#the-reader + 6. https://littleosbook.github.io/#credits-thanks-and-acknowledgements + 7. https://littleosbook.github.io/#contributors + 8. https://littleosbook.github.io/#changes-and-corrections + 9. https://littleosbook.github.io/#issues-and-where-to-get-help + 10. https://littleosbook.github.io/#license + 11. https://littleosbook.github.io/#first-steps + 12. https://littleosbook.github.io/#tools + 13. https://littleosbook.github.io/#quick-setup + 14. https://littleosbook.github.io/#programming-languages + 15. https://littleosbook.github.io/#host-operating-system + 16. https://littleosbook.github.io/#build-system + 17. https://littleosbook.github.io/#virtual-machine + 18. https://littleosbook.github.io/#booting + 19. https://littleosbook.github.io/#bios + 20. https://littleosbook.github.io/#the-bootloader + 21. https://littleosbook.github.io/#the-operating-system + 22. https://littleosbook.github.io/#hello-cafebabe + 23. https://littleosbook.github.io/#compiling-the-operating-system + 24. https://littleosbook.github.io/#linking-the-kernel + 25. https://littleosbook.github.io/#obtaining-grub + 26. https://littleosbook.github.io/#building-an-iso-image + 27. https://littleosbook.github.io/#running-bochs + 28. https://littleosbook.github.io/#further-reading + 29. https://littleosbook.github.io/#getting-to-c + 30. https://littleosbook.github.io/#setting-up-a-stack + 31. https://littleosbook.github.io/#calling-c-code-from-assembly + 32. https://littleosbook.github.io/#packing-structs + 33. https://littleosbook.github.io/#compiling-c-code + 34. https://littleosbook.github.io/#build-tools + 35. https://littleosbook.github.io/#further-reading-1 + 36. https://littleosbook.github.io/#output + 37. https://littleosbook.github.io/#interacting-with-the-hardware + 38. https://littleosbook.github.io/#the-framebuffer + 39. https://littleosbook.github.io/#writing-text + 40. https://littleosbook.github.io/#moving-the-cursor + 41. https://littleosbook.github.io/#the-driver + 42. https://littleosbook.github.io/#the-serial-ports + 43. https://littleosbook.github.io/#configuring-the-serial-port + 44. https://littleosbook.github.io/#configuring-the-line + 45. https://littleosbook.github.io/#configuring-the-buffers + 46. https://littleosbook.github.io/#configuring-the-modem + 47. https://littleosbook.github.io/#writing-data-to-the-serial-port + 48. https://littleosbook.github.io/#configuring-bochs + 49. https://littleosbook.github.io/#the-driver-1 + 50. https://littleosbook.github.io/#further-reading-2 + 51. https://littleosbook.github.io/#segmentation + 52. https://littleosbook.github.io/#accessing-memory + 53. https://littleosbook.github.io/#the-global-descriptor-table-gdt + 54. https://littleosbook.github.io/#loading-the-gdt + 55. https://littleosbook.github.io/#further-reading-3 + 56. https://littleosbook.github.io/#interrupts-and-input + 57. https://littleosbook.github.io/#interrupts-handlers + 58. https://littleosbook.github.io/#creating-an-entry-in-the-idt + 59. https://littleosbook.github.io/#handling-an-interrupt + 60. https://littleosbook.github.io/#creating-a-generic-interrupt-handler + 61. https://littleosbook.github.io/#loading-the-idt + 62. https://littleosbook.github.io/#programmable-interrupt-controller-pic + 63. https://littleosbook.github.io/#reading-input-from-the-keyboard + 64. https://littleosbook.github.io/#further-reading-4 + 65. https://littleosbook.github.io/#the-road-to-user-mode + 66. https://littleosbook.github.io/#loading-an-external-program + 67. https://littleosbook.github.io/#grub-modules + 68. https://littleosbook.github.io/#executing-a-program + 69. https://littleosbook.github.io/#a-very-simple-program + 70. https://littleosbook.github.io/#compiling + 71. https://littleosbook.github.io/#finding-the-program-in-memory + 72. https://littleosbook.github.io/#jumping-to-the-code + 73. https://littleosbook.github.io/#the-beginning-of-user-mode + 74. https://littleosbook.github.io/#a-short-introduction-to-virtual-memory + 75. https://littleosbook.github.io/#virtual-memory-through-segmentation + 76. https://littleosbook.github.io/#further-reading-5 + 77. https://littleosbook.github.io/#paging + 78. https://littleosbook.github.io/#why-paging + 79. https://littleosbook.github.io/#paging-in-x86 + 80. https://littleosbook.github.io/#identity-paging + 81. https://littleosbook.github.io/#enabling-paging + 82. https://littleosbook.github.io/#a-few-details + 83. https://littleosbook.github.io/#paging-and-the-kernel + 84. https://littleosbook.github.io/#reasons-to-not-identity-map-the-kernel + 85. https://littleosbook.github.io/#the-virtual-address-for-the-kernel + 86. https://littleosbook.github.io/#placing-the-kernel-at-0xc0000000 + 87. https://littleosbook.github.io/#higher-half-linker-script + 88. https://littleosbook.github.io/#entering-the-higher-half + 89. https://littleosbook.github.io/#running-in-the-higher-half + 90. https://littleosbook.github.io/#virtual-memory-through-paging + 91. https://littleosbook.github.io/#further-reading-6 + 92. https://littleosbook.github.io/#page-frame-allocation + 93. https://littleosbook.github.io/#managing-available-memory + 94. https://littleosbook.github.io/#how-much-memory-is-there + 95. https://littleosbook.github.io/#managing-available-memory-1 + 96. https://littleosbook.github.io/#how-can-we-access-a-page-frame + 97. https://littleosbook.github.io/#a-kernel-heap + 98. https://littleosbook.github.io/#further-reading-7 + 99. https://littleosbook.github.io/#user-mode + 100. https://littleosbook.github.io/#segments-for-user-mode + 101. https://littleosbook.github.io/#setting-up-for-user-mode + 102. https://littleosbook.github.io/#entering-user-mode + 103. https://littleosbook.github.io/#using-c-for-user-mode-programs + 104. https://littleosbook.github.io/#a-c-library + 105. https://littleosbook.github.io/#further-reading-8 + 106. https://littleosbook.github.io/#file-systems + 107. https://littleosbook.github.io/#why-a-file-system + 108. https://littleosbook.github.io/#a-simple-read-only-file-system + 109. https://littleosbook.github.io/#inodes-and-writable-file-systems + 110. https://littleosbook.github.io/#a-virtual-file-system + 111. https://littleosbook.github.io/#further-reading-9 + 112. https://littleosbook.github.io/#system-calls + 113. https://littleosbook.github.io/#designing-system-calls + 114. https://littleosbook.github.io/#implementing-system-calls + 115. https://littleosbook.github.io/#further-reading-10 + 116. https://littleosbook.github.io/#multitasking + 117. https://littleosbook.github.io/#creating-new-processes + 118. https://littleosbook.github.io/#cooperative-scheduling-with-yielding + 119. https://littleosbook.github.io/#preemptive-scheduling-with-interrupts + 120. https://littleosbook.github.io/#programmable-interval-timer + 121. https://littleosbook.github.io/#separate-kernel-stacks-for-processes + 122. https://littleosbook.github.io/#difficulties-with-preemptive-scheduling + 123. https://littleosbook.github.io/#further-reading-11 + 124. https://littleosbook.github.io/#first-steps + 125. https://littleosbook.github.io/#getting-to-c + 126. https://littleosbook.github.io/#output + 127. https://littleosbook.github.io/#segmentation + 128. https://littleosbook.github.io/#interrupts-and-input + 129. https://littleosbook.github.io/#the-road-to-user-mode + 130. https://littleosbook.github.io/#a-short-introduction-to-virtual-memory + 131. https://littleosbook.github.io/#paging + 132. https://littleosbook.github.io/#page-frame-allocation + 133. https://littleosbook.github.io/#user-mode + 134. https://littleosbook.github.io/#file-systems + 135. https://littleosbook.github.io/#system-calls + 136. https://littleosbook.github.io/#multitasking + 137. http://progit.org/ + 138. https://github.com/alexschneider + 139. https://github.com/Avidanborisov + 140. https://github.com/nirs + 141. https://github.com/kedarmhaswade + 142. https://github.com/vamanea + 143. https://github.com/ansjob + 144. https://github.com/littleosbook/littleosbook/issues + 145. http://creativecommons.org/licenses/by-nc-sa/3.0/us/ + 146. https://littleosbook.github.io/#fn1 + 147. https://littleosbook.github.io/#getting-to-c + 148. ftp://alpha.gnu.org/gnu/grub/grub-0.97.tar.gz + 149. http://littleosbook.github.com/files/stage2_eltorito + 150. http://duartes.org/gustavo/blog/post/how-computers-boot-up + 151. http://duartes.org/gustavo/blog/post/kernel-boot-process + 152. http://wiki.osdev.org/Boot_Sequence + 153. https://littleosbook.github.io/#the-framebuffer + 154. http://en.wikibooks.org/wiki/Serial_Programming/8250_UART_Programming#UART_Registers + 155. http://wiki.osdev.org/Serial_ports + 156. https://littleosbook.github.io/#paging + 157. https://littleosbook.github.io/#packing-structs + 158. http://wiki.osdev.org/Segmentation + 159. http://en.wikipedia.org/wiki/X86_memory_segmentation + 160. https://littleosbook.github.io/#getting-to-c + 161. http://wiki.osdev.org/Interrupts + 162. https://littleosbook.github.io/#scheduling + 163. https://littleosbook.github.io/#paging + 164. http://www.gnu.org/software/grub/manual/multiboot/html_node/multiboot.h.html + 165. https://littleosbook.github.io/#segmentation + 166. https://littleosbook.github.io/#paging + 167. https://littleosbook.github.io/#page-frame-allocation + 168. https://littleosbook.github.io/#paging + 169. https://littleosbook.github.io/#page-frame-allocation + 170. http://lwn.net/Articles/253361/ + 171. http://duartes.org/gustavo/blog/post/memory-translation-and-segmentation + 172. https://littleosbook.github.io/#user-mode + 173. https://littleosbook.github.io/#linking-the-kernel + 174. https://littleosbook.github.io/#linking-the-kernel + 175. https://littleosbook.github.io/#page-frame-allocation + 176. http://en.wikipedia.org/wiki/Paging + 177. http://wiki.osdev.org/Paging + 178. http://wiki.osdev.org/Higher_Half_bare_bones + 179. http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory + 180. http://flint.cs.yale.edu/cs422/doc/ELF_Format.pdf + 181. http://wiki.osdev.org/Page_Frame_Allocation + 182. https://littleosbook.github.io/#the-global-descriptor-table-gdt + 183. https://littleosbook.github.io/#segmentation + 184. https://littleosbook.github.io/#system-calls + 185. https://littleosbook.github.io/#creating-and-loading-the-gdt + 186. https://littleosbook.github.io/#system-calls + 187. http://duartes.org/gustavo/blog/post/cpu-rings-privilege-and-protection + 188. https://littleosbook.github.io/#further-reading-6 + 189. https://littleosbook.github.io/#further-reading-6 + 190. http://plan9.bell-labs.com/plan9/index.html + 191. http://en.wikipedia.org/wiki/Inode + 192. http://en.wikipedia.org/wiki/Inode_pointer_structure + 193. http://www.arl.wustl.edu/~fredk/Courses/cs523/fall01/Papers/kleiman86vnodes.pdf + 194. http://static.usenix.org/publications/library/proceedings/bsdcon02/full_papers/kamp/kamp_html/index.html + 195. https://littleosbook.github.io/#further-reading-7 + 196. https://littleosbook.github.io/#user-mode + 197. https://littleosbook.github.io/#entering-user-mode + 198. http://en.wikipedia.org/wiki/POSIX + 199. http://bluemaster.iu.hio.no/edu/dark/lin-asm/syscalls.html + 200. http://en.wikipedia.org/wiki/System_call + 201. https://littleosbook.github.io/#setting-up-for-user-mode + 202. https://littleosbook.github.io/#user-mode + 203. https://littleosbook.github.io/#entering-user-mode + 204. https://littleosbook.github.io/#user-mode + 205. http://wiki.osdev.org/Scheduling_Algorithms + 206. http://www.kth.se/ + 207. http://en.wikipedia.org/wiki/Hexadecimal + 208. http://wiki.osdev.org/Main_Page + 209. http://www.jamesmolloy.co.uk/tutorial_html/ + 210. http://www.ubuntu.com/ + 211. http://www.virtualbox.org/ + 212. http://en.wikipedia.org/wiki/C_(programming_language) + 213. http://gcc.gnu.org/ + 214. http://www.nasm.us/ + 215. http://en.wikipedia.org/wiki/Bash_%28Unix_shell%29 + 216. http://www.gnu.org/software/make/ + 217. http://bochs.sourceforge.net/ + 218. http://wiki.qemu.org/Main_Page + 219. https://en.wikipedia.org/wiki/BIOS + 220. http://www.gnu.org/software/grub/ + 221. http://en.wikipedia.org/wiki/Executable_and_Linkable_Format + 222. http://www.gnu.org/software/grub/manual/multiboot/multiboot.html + 223. http://www.gnu.org/software/binutils/ + 224. https://bugs.launchpad.net/ubuntu/+source/grub/+bug/426419 + 225. http://en.wikipedia.org/wiki/ISO_image + 226. http://bochs.sourceforge.net/doc/docbook/user/bochsrc.html + 227. http://www.nasm.us/doc/nasmdoc3.htm + 228. http://en.wikipedia.org/wiki/X86_calling_conventions + 229. http://en.wikipedia.org/wiki/Framebuffer + 230. http://en.wikipedia.org/wiki/VGA-compatible_text_mode + 231. https://en.wikipedia.org/wiki/Ascii + 232. http://wiki.osdev.org/VGA_Hardware + 233. http://en.wikipedia.org/wiki/Serial_port + 234. http://wiki.osdev.org/Serial_ports + 235. http://en.wikibooks.org/wiki/Serial_Programming/8250_UART_Programming + 236. http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-3a-part-1-manual.html/ + 237. http://www.nasm.us/doc/nasmdoc4.html#section-4.3 + 238. http://www.acm.uiuc.edu/sigops/roll_your_own/i386/irq.html + 239. http://www.win.tue.nl/ + 240. http://www.math.utah.edu/docs/info/ld_toc.html + 241. http://wiki.osdev.org/Page_Frame_Allocation + 242. http://wiki.osdev.org/Programmable_Interval_Timer + 243. https://littleosbook.github.io/#fnref1 |